Languages

• Finite State Automata are also called Finite State Machines.
• FSAs can be used to recognise and generate regular languages.

Current State	Input	Next State
S0	a	S1
S1	b	S1
S1	a	S2
S2	c	S3

• This can be used to generate or recognise the language ab*ac
• The start state is S0
• To generate, start at S0, and choose any option from the current state.
• You finish in S3.
• To recognise, start at S0, and read the input following the transitions.
• If you are in S3 when the last input comes (and you've only made named transitions), the input is an element of the language.
• Note that S3 is called the final state.
• The class of languages that can be generated (or recognised) by some FSA is called the regular languages.
• These types of languages are called formal languages. Languages like English, Urdu, Chinese and French are called natural.
• Natural languages are thought to be Context Free but it has been argued reasonably (e.g. Blank) that they are regular.