7 1. FSA 8
1. FSA
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Classes of Language/Machine: Context-free Languages
• No finite state automaton can be designed to accept the languages of addition and subtraction. • They belong to the class of context-free languages (a class that includes most programming languages). • To recognise a context-free language requires the power of the class of machines called push-down automata. • Note that push-down automata can also recognise the regular languages. 1. FSA 9
1. FSA
1
1. FSA
2
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Languages and Machines
• A language is typically defined as a set of words. • Words are strings containing the symbols in some alphabet. • The machines to be considered are those that compute by: – accepting all the strings in some language, and – rejecting all others.
1. FSA
1
9/27/10
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Example Language 2
• If the numbers 1-30 are assigned, then the machine would be unable to distinguish the code 1 from the code 11. • This problem would be avoided if the numbers 10-39 are used, each of which has exactly two digits.
9/27/10
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Contents 1. State Machines and Finite State Automata
• • • • Languages and machines Deterministic FSA and transition diagrams Non-deterministic FSA Comparing DFSA and NFSA
Classes of Language/Machine: Regular Languages
• Language 2 belongs to the class of regular languages. • Language 1 does not. • For every regular language, an acceptor machine can be constructed that belongs to the class of machines called finite state automata. • (Note: one automaton, many automata.)
1. FSA
12
2
9/27/10
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Finite state automata
• If the machine is in one of the accept states (also called favourable states) when the string of input symbols comes to an end, then the input is accepted, or recognised (as a member of the language to be recognised), otherwise it is rejected.
Jacob Howe: IN3017, Theory of Computation
Jacob Howe: IN3017, Theory of Computation
Finite state automata (informal)
• A finite state automaton (FSA) consists of – a finite set of states and – a finite set of transitions from state to state, each of which is associated with a symbol from an alphabet. • One state is the initial state, in which the automaton starts. • Some (or no) states are designated as accepting states.
Transition diagrams
• Any FSA may be represented by its transition diagram. • This is a directed graph in which – each state is denoted by circle – each transition is denoted by an edge between two states, labelled by the associated symbol, – the start state is indicated by an incoming arrow – the accepting state(s) are denoted by a 1. FSA double circle.
Classes of Language/Machine: Context-sensitive Languages
• The push-down automata are also limited in their computational power, that is, – in the class of languages they can recognise, • or equivalently, – in the class of functions they can compute. • They cannot recognise the context-sensitive languages, which require the power of Turing Machines. E.g. anbmanbm • This class of machine is the most powerful. In fact, no function that cannot be computed by a Turing Machine can be computed at all! 1. FSA 10
1. FSA 11
Finite state automata (formal)
• A Deterministic Finite State Automaton is a 5-tuple, (Q, Σ, δ, q0, F), where: – Q is a finite set of states – Σ is a finite input alphabet (set of symbols) – δ is the transition function, Q×Σ→Q, that determines, for each state and for each symbol of the alphabet, the next state. – q0 is the initial state (or start state), q0∈Q – F is the set of accept states (F⊆Q).
1. FSA 5
Example Language 2
• A vending machine supplies 30 products (Mars bars etc.) and has a numeric keypad with digits 0-9. • The machine works by accepting the input language (the vending code) and then delivering the relevant product. • What code should be assigned to each product?
1. FSA 3
Example Language 1:
• The set of all words of the form: ambncm+n, where – m, n range over the natural numbers 0, 1, 2,... – xn denotes the string containing n successive copies of the symbol x. • The alphabet of this language is the set {a,b,c}. • Here are some valid words in this language: – aaabbccccc aabbcccc • Some words with the same alphabet but not in this language: – aabbcc abccc bbaccc • 1.This language might be said to represent addition . FSA 4