Introduction
No computation model can compute more than a computer. However, there are computations that
a computer cannot compute. The first computation mechanism was invented by Alan Turing in,
namely Turing Machines: an abstract computation model, automata with read/write tape. This is a
universal computation mechanism, it is invented before the computer. Everything a computer can
compute; a Turing machine can compute as well. by studying the Turing
machine, we can find the limitations.
Finite automata give rise to regular languages (one can be transformed into the other):
- Application: pattern recognition
- Equivalent to: regular expressions, regular grammars
Pushdown automata: give rise to context-free languages:
- Application: parsing (e.g., programming languages)
- Equivalent to context-free grammars
Turing machines yield recursively enumerable languages:
- Application: general computation
Automata are Ubiquitous. Some (at first glance simple) problems are undecidable (when should a
program terminate). Some problems (NP-hard problems) are (probably, no mathematical proof) not
efficiently solvable by a computer (TS problem).
Aspects of languages:
- Syntax: the form of the words in the language
- Semantics: the meaning of the words in the language
Languages
Word = finite sequence of symbols from an alphabet ∑
- Notation for symbols: a, b, c
- Notation for words: u, v, w
- a∊∑ means a is a symbol from the alphabet ∑
- λ is the empty word and is NOT a letter of the alphabet (“”)
Everything stored on a computer is a word (sequence of bits). A bit can either be 0 or 1 → ∑ = {0, 1}.
In particular, a computer program is a word. From an abstract point of view, a program: takes a
word as input and produces it to a word as output. A program can be given itself as input.
Operations on words:
- Concatenation: if v = a1…an and w = b1…bm then vw = a1…anb1…bm
- Length: if v = a1…an then |v| = n. |λ| = 0 and |va| = |v| + 1.
- Power: vk consists of k concatenations of v’s. v0 = λ and vk+1 = vkv.
- Reverse: reverse of a1…an is (a1…an)R = an…a1. λR = λ and (va)R-= a(v)R.
,A formal language is a set of words. A formal language L is a subset of ∑*, that is L ⊆ ∑*. Here ∑* is
the set of all words over ∑. The set of all parseable C programs form a language. {ab, aab,
babababab} is a finite language over ∑ = {a, b}. {abna | n >= 1} is an infinite language over ∑ = {a, b}:
{aba, abba, abbba, …}. {anbn | n >= 0} is an infinite language over ∑ = {a, b}: {λ, ab, aabb,…}.
A language is a set of words, so the usual set operations have meaning for the language. \ is the
difference operator. The complement =all words that are not in the language L: = ∑*\L. For ∑
= {a} and L = {a, aaa} then {λ, aa} UNIION {an|n>=4}. The reverse of a language L = LR = {xR|x∊L}.
R
The reverse of L = {λ, ab} is L = {λ , ba}. Concatenation of languages L1 and L2 is defined as L1L2 = {xy |
x ∊L1 AND y∊L2}. The n-th power of language L is defined by induction on n: L0 = {λ}, this language
consists of 1 word, namely the empty word and Ln+1 = LnL (n>=0).
Kleene star: L* = L+ UNIUON λ. L* are all the words that you
can build from ‘building blcoks’ L. If L contains the empty word, L+ and L* will be the same.
difficult to write it down like this (sets)
Finite Automata
Deterministic Finite Automata (DFA)
Deterministic finite automaton, short DFA, consists of:
- A finite set Q of states
- A finite input alphabet ∑
- A transition function δ: Q x ∑ → Q. If the automaton in state q reads the symbol a than the
resulting state is δ(q, a)
- A starting state qo ∊ Q
- A set of F ⊆ of final states
Let M = Q, ∑, δ, q0, F) be a DFA. A configuration of M is a pair (q, w) with q∊Q and w∊∑*. you are in
state q and gets as input w. So (q, w) means the automaton is in state q and reads word w. The step
relation |-- is defined on configurations by (q, aw) |-- (q’, w) if δ(q, a) = q’. The step relation is
basically the execution of the automaton. After reading (q0, a) |-- (q0, λ).
We define |--* as the reflexive transitive closure of |-- (basically from beginning to a state). |-- can
be either 0 or more steps. Transition functions can be written in the form of a table.
A DFA can be visualized as a transition graph, consisting of:
- States are the nodes of the graph.
o Starting state is indicated by an extra incoming arrow
, o Final states are indicated by a double circle
- Arrows with labels from ∑:
An arrow with label a, b is shorthand for 2 arrows: one with label a and one with label b.
For a word w = a1…an >= 0, we write (from q0 to qn with a word) if there are states
q1…qn-1 such that Every path
has the empty word as path to itself (arrow with λ).
Theorem:
A language L is regular if there exists a DFA M with L(M) = L
DFAs are deterministic: for every state q ∊ Q and every symbol a ∊∑, the state q has precisely one
outgoing arrow with label a.
If L is a regular language, then the complement of L is also regular. The graph can be obtained by
simply changing the final states to non-final states and vice versa. If L1 and L2 are regular, then
L1 UNION L2 is regular. The graph can be obtained by:
The only differences between UNION and AND is that the goal states are now the goal states where
both q1 and q2 are goal states. The only differences between UNION and DIFF is that the goal states
are now the goal states where either q1 or q2 is a goal state. Hence, if L1 and L2 are regular then the
UNION, DIFF and AND are regular.
Every finite language L is regular.
, Minimal DFAs
States q1, q2 are distinguishable if there exists a word such that you can go from q1 to q1’ but not
from q2 to q2’ (there is a word that is accepted by one state but not by the other). The algorithm to
construct the minimal DFA (hopcroft’s algorithm):
The minimal DFA accepting a given language L is unique to isomorphism (renaming the states). 2
DFAs accept the same language iff their minimal DFAs coincide up to isomorphism.
An automaton is complete if every state q has an outgoing transition for every input letter a. The
DFAs in this course are always complete.
An automaton is deterministic if for every input word, there is a unique path (sequence of
transitions) through the automaton when reading the word. In particular, there exists no state q
having 2 outgoing transitions with the same label a∊∑.
Nondeterministic Finite Automata (NFA)
NFAs are defined like DFAs, except that NFAs allow for:
- Multiple starting states
No computation model can compute more than a computer. However, there are computations that
a computer cannot compute. The first computation mechanism was invented by Alan Turing in,
namely Turing Machines: an abstract computation model, automata with read/write tape. This is a
universal computation mechanism, it is invented before the computer. Everything a computer can
compute; a Turing machine can compute as well. by studying the Turing
machine, we can find the limitations.
Finite automata give rise to regular languages (one can be transformed into the other):
- Application: pattern recognition
- Equivalent to: regular expressions, regular grammars
Pushdown automata: give rise to context-free languages:
- Application: parsing (e.g., programming languages)
- Equivalent to context-free grammars
Turing machines yield recursively enumerable languages:
- Application: general computation
Automata are Ubiquitous. Some (at first glance simple) problems are undecidable (when should a
program terminate). Some problems (NP-hard problems) are (probably, no mathematical proof) not
efficiently solvable by a computer (TS problem).
Aspects of languages:
- Syntax: the form of the words in the language
- Semantics: the meaning of the words in the language
Languages
Word = finite sequence of symbols from an alphabet ∑
- Notation for symbols: a, b, c
- Notation for words: u, v, w
- a∊∑ means a is a symbol from the alphabet ∑
- λ is the empty word and is NOT a letter of the alphabet (“”)
Everything stored on a computer is a word (sequence of bits). A bit can either be 0 or 1 → ∑ = {0, 1}.
In particular, a computer program is a word. From an abstract point of view, a program: takes a
word as input and produces it to a word as output. A program can be given itself as input.
Operations on words:
- Concatenation: if v = a1…an and w = b1…bm then vw = a1…anb1…bm
- Length: if v = a1…an then |v| = n. |λ| = 0 and |va| = |v| + 1.
- Power: vk consists of k concatenations of v’s. v0 = λ and vk+1 = vkv.
- Reverse: reverse of a1…an is (a1…an)R = an…a1. λR = λ and (va)R-= a(v)R.
,A formal language is a set of words. A formal language L is a subset of ∑*, that is L ⊆ ∑*. Here ∑* is
the set of all words over ∑. The set of all parseable C programs form a language. {ab, aab,
babababab} is a finite language over ∑ = {a, b}. {abna | n >= 1} is an infinite language over ∑ = {a, b}:
{aba, abba, abbba, …}. {anbn | n >= 0} is an infinite language over ∑ = {a, b}: {λ, ab, aabb,…}.
A language is a set of words, so the usual set operations have meaning for the language. \ is the
difference operator. The complement =all words that are not in the language L: = ∑*\L. For ∑
= {a} and L = {a, aaa} then {λ, aa} UNIION {an|n>=4}. The reverse of a language L = LR = {xR|x∊L}.
R
The reverse of L = {λ, ab} is L = {λ , ba}. Concatenation of languages L1 and L2 is defined as L1L2 = {xy |
x ∊L1 AND y∊L2}. The n-th power of language L is defined by induction on n: L0 = {λ}, this language
consists of 1 word, namely the empty word and Ln+1 = LnL (n>=0).
Kleene star: L* = L+ UNIUON λ. L* are all the words that you
can build from ‘building blcoks’ L. If L contains the empty word, L+ and L* will be the same.
difficult to write it down like this (sets)
Finite Automata
Deterministic Finite Automata (DFA)
Deterministic finite automaton, short DFA, consists of:
- A finite set Q of states
- A finite input alphabet ∑
- A transition function δ: Q x ∑ → Q. If the automaton in state q reads the symbol a than the
resulting state is δ(q, a)
- A starting state qo ∊ Q
- A set of F ⊆ of final states
Let M = Q, ∑, δ, q0, F) be a DFA. A configuration of M is a pair (q, w) with q∊Q and w∊∑*. you are in
state q and gets as input w. So (q, w) means the automaton is in state q and reads word w. The step
relation |-- is defined on configurations by (q, aw) |-- (q’, w) if δ(q, a) = q’. The step relation is
basically the execution of the automaton. After reading (q0, a) |-- (q0, λ).
We define |--* as the reflexive transitive closure of |-- (basically from beginning to a state). |-- can
be either 0 or more steps. Transition functions can be written in the form of a table.
A DFA can be visualized as a transition graph, consisting of:
- States are the nodes of the graph.
o Starting state is indicated by an extra incoming arrow
, o Final states are indicated by a double circle
- Arrows with labels from ∑:
An arrow with label a, b is shorthand for 2 arrows: one with label a and one with label b.
For a word w = a1…an >= 0, we write (from q0 to qn with a word) if there are states
q1…qn-1 such that Every path
has the empty word as path to itself (arrow with λ).
Theorem:
A language L is regular if there exists a DFA M with L(M) = L
DFAs are deterministic: for every state q ∊ Q and every symbol a ∊∑, the state q has precisely one
outgoing arrow with label a.
If L is a regular language, then the complement of L is also regular. The graph can be obtained by
simply changing the final states to non-final states and vice versa. If L1 and L2 are regular, then
L1 UNION L2 is regular. The graph can be obtained by:
The only differences between UNION and AND is that the goal states are now the goal states where
both q1 and q2 are goal states. The only differences between UNION and DIFF is that the goal states
are now the goal states where either q1 or q2 is a goal state. Hence, if L1 and L2 are regular then the
UNION, DIFF and AND are regular.
Every finite language L is regular.
, Minimal DFAs
States q1, q2 are distinguishable if there exists a word such that you can go from q1 to q1’ but not
from q2 to q2’ (there is a word that is accepted by one state but not by the other). The algorithm to
construct the minimal DFA (hopcroft’s algorithm):
The minimal DFA accepting a given language L is unique to isomorphism (renaming the states). 2
DFAs accept the same language iff their minimal DFAs coincide up to isomorphism.
An automaton is complete if every state q has an outgoing transition for every input letter a. The
DFAs in this course are always complete.
An automaton is deterministic if for every input word, there is a unique path (sequence of
transitions) through the automaton when reading the word. In particular, there exists no state q
having 2 outgoing transitions with the same label a∊∑.
Nondeterministic Finite Automata (NFA)
NFAs are defined like DFAs, except that NFAs allow for:
- Multiple starting states
