Formal Languages and Automata
Text Book:
“Theory of Computation an Introduction" by James L. Hein, Jones & Bartlett
Publishers 1996; ISBN: 0-86720-497-4.
1
Meaning of Ambiguity
◼ A grammar is called ambiguous if its language contains
some string that has two different parse trees.
◼ Suppose we define a set of arithmetic expressions by the
grammar,
E → a | b | E-E .
◼ This grammar is ambiguous because it has a string a-b-a
that has two distinct leftmost derivations.
E ⇒ E-E ⇒ a-E ⇒ a-E-E ⇒ a-b-E ⇒ a-b-a.
E ⇒ E- E ⇒ E-E-E ⇒ a-E-E ⇒ a-b-E ⇒ a-b-a.
2
What is Regular language?
◼ The language is regular if there is a finite accepter
or automaton for it. Therefore, every regular
language can be described by some DFA or NFA.
◼ What is the Automata?
It is an abstract model of a digital computer.
3
◼ Input file: set of cells each cell contains one symbol; the automaton can read
but not change.
◼ Output: some actions or any form based on the input and the control unit
internal state.
◼ Storage: it is a temporary storage device consisting of unlimited number of
cells each cell holding only a single symbol from an alphabet (not
necessarily the same input one).
◼ Control unit: can be in any one of a finite number of internal states, and
which can change state in some definite manners using specific transition
function, which in turn, gives the next state in terms of the current state.
◼ Configuration: This term is used to refer to a particular state of the control
unit, input file, and temporary storage.
◼ Move: is the transition of the automaton from one configuration to the next.
Input file
Control unit Storage
Output
4
Types of automata
◼ We have two types of automata deterministic and nondeterministic.
◼ Deterministic automata:
Each move is uniquely determined by the current configuration; if we know the
internal state, the input, and the contents of the temporary storage, we can
predict the future behavior of the automaton exactly.
◼ Nondeterministic automata:
At each point, a nondeterministic automaton may have several possible moves,
so we can only predict a set of possible actions.
◼ Accepter: an automaton whose response is limited to a simple “yes” or “No”.
Presented with input string, an accepter either accepts or rejects it.
◼ Transducers: a more general automaton that capable of producing strings of
symbols as output.
5
what we study is not just a collection of abstractions
◼ Example:
This is a smaller part of the compiler of the C or Pascal to define the identifiers (variable
or constant names):
<id> → <letter> <rest>,
<rest> → <letter><rest> | <digital><rest> | .
<letter> → a| b| …| z.
<digital> → 0| 1| …|9.
◼ In this example the terminals are a,b,..,z and 0,1,…,9. However, the nonterminals are
<id>, <letter>, <rest> and <digital>.
◼ The derivation of the identifier a0 is:
<id> ⇒ <letter> <rest>
⇒ a <rest>
⇒ a <digital> <rest>
⇒ a 0 <rest>
⇒ a 0.
6
How can we represent this identifier in the
form of automaton???
◼ An automaton can be represented by a graph in which the vertices
give the internal states and the edges transitions. The label on the
edges shows what happens (in terms of input and output) during the
transition.
letter
1 2
digit Letters or digit
Letters or digit
7
Deterministic Finite Automata (DFA)
◼ Example:
b
a 1 a
0 3 a, b
a
b b
2
The above automaton accepts the strings aba, baaabab.
However it rejects any string of the form abn.
8
Deterministic Finite Automata (DFA)
◼ Formally, we can define Deterministic Finite Automata
as the quintuple
M = (Q, , , q0, F), where
◼ Q : is a finite set of internal states.
◼ : is a finite set of symbols, called input alphabet.
◼ : Q X → Q is a total function called the transition
function.
◼ q0 Q is the initial state.
◼ F Q is a set of final states.
9
DFA
Example
◼ M =({q0, q1, q2}, {0,1}, , q0, {q1}), where is
(q0, 0) = q0 (q0, 1) = q1 (q1, 0) = q0
(q1, 1) = q2 (q2, 0) = q2 (q2, 1) = q1
0 1
0 0
q0 q1 q2
1 1
10
Deterministic finite automata (DFA)
◼ Informally, a deterministic finite automaton over an alphabet
A can be thought of as a finite directed graph with the property
that each node emits one labeled edge for each distinct element
of A, the nodes are called states. There is one special state
called the start or the initial state, and there is at least one final
state.
◼ A DFA accepts a string w in A* if there is a path from the start
state to some final states such that w is the concatenation of
the labels on the edges of the path. Otherwise, the DFA rejects
w. the set of all strings accepted by a DFA M is called the
language of M and denoted by L(M).
11
Languages and DFA
◼ The language accepted by a dfa M = (Q, , , q0, F) is
the set of all strings on accepted by M.
Formally,
L(M) = {w * : *(q0, w) F}
L(M) = {w * : *(q0, w) F} non accepted words
where * : Q X * → Q is the extended transition function.
The second argument of * is a string rather than a single
symbol, and its value gives the state the automaton will be in
after reading that string.
12
Examples
q0
= {a, b} a b = {a, b}
b a
a a q1 q3 b
q0 q1
b b a a b
b q2 q4 a
0 1 0, 1
q0 1 q1 0 q2
= {0, 1}
What are the languages of these automata?
13
Examples
◼ Construct a DFA over alphabet {0, 1} that accepts
all strings that end in 01 0
0 q 00
◼ Answer: 0 q 1
1
0 q01
0
q 0 1
1
1 q10
0
q1 0
1
q11
1
14
Languages and Dfa’s
◼ Example:
a a,b
q0 b q1 a, b q2
trap state
L = { anb: n >= 0}
15
Deterministic Finite Automata
❑ Find a deterministic finite accepter that recognizes the set of all
strings on = {a, b} staring with a prefix ab.
a,b
q0 a q1 b q2
b a
q3 a,b
❑ Find a dfa that accepts all strings on {0, 1}, except those containing
the substring 001.
1 0 0,1
1
⋀ 0 0 00 1 001
0
16
Deterministic Finite Automata
• for ∑ = {a,b}, construct a DFA that accept the sets consisting
of all strings with no more than three a's.
17
Deterministic Finite Automata
• design the DFA that defines the language L= {ab5wb2: w
ϵ{a,b}*}
18
Regular Languages
❑ Definition: A language L is called regular language if and only if
there exits some dfa M such that L = L(M).
❑ Example : show that L = {awa: w {a, b}*} is regular.
b a
b
a q2 q3
q0
b a
a, b
19
20
