FORMAL LANGUAGES AND AUTOMATA

THEORY

Module 1 – Complete Notes

Automata theory

• Automata theory is the study of abstract computing devices, or "machines."

• Before there were computers, in the 1930's, A. Turing studied an abstract machine
that had all the capabilities of today's computers, at least as far as in what they
could compute.
• Turing's goal was to describe precisely the boundary between what a computing
machine could do and what it could not do; his conclusions apply not only to his
abstract Turing machines, but to today's real machines.
Automata theory
Automata theory
• Also in the late 1950's, the linguist N. Chomsky began the study of
formal "grammars."
• While not strictly machines, these grammars have close relationships
to abstract automata and serve today as the basis of some important
software components, including parts of compilers.
Introduction to Finite Automata
Finite automata are a useful model for many important kinds of hardware and
software.
1. Software for designing and checking the behavior of digital circuits.
2. The "lexical analyzer" of a typical compiler, that is, the compiler component that breaks the input text into
logical units, such as identifiers, keywords, and punctuation.
3. Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words,
phrases, or other patterns.
4. Software for verifying systems of all types that have a finite number of distinct states, such as
communications protocols or protocols for secure exchange of information.
The Central Concepts of Automata Theory

These concepts include the

• “Alphabet" - a set of symbols,
• “Strings" - a list of symbols from an alphabet, and
• “Language" - a set of strings from the same alphabet.
Alphabets

• An alphabet is a finite, nonempty set of symbols.

• Conventionally, we use the symbol Σ for an alphabet.
• Σ ={0, 1}, the binary alphabet.
• Σ = {a, b, ... , z}, the set of all lower-case letters.
• The set of all ASCII characters, or the set of all printable ASCII characters.
Strings

• A string (or sometimes word) is a finite sequence of symbols chosen from some
alphabet.
• For example, 01101 is a string from the binary alphabet Σ = {0, 1}.
• The string 111 is another string chosen from this alphabet.
Strings
The Empty String

• The empty string is the string with zero occurrences of symbols.

• This string, denoted ε , is a string that may be chosen from any alphabet
whatsoever.
Strings
Length of a String

• It is often useful to classify strings by their length, that is, the number of positions
for symbols in the string.
• For instance, 01101 has length 5.
• The standard notation for the length of a string w is |w|.
• For example, | 011 |= 3 and | ε |=0.
Strings
Powers of an Alphabet

• If Σ is an alphabet, we can express the set of all strings of a certain length from
that alphabet by using an exponential notation.
• We define ∑n to be the set of strings of length n, each of whose symbols is in Σ.
Strings
Powers of an Alphabet

For example,
• Σ ={0,1}
• Σ0 = {ε}
• Σ1= {0,1} ( 21=2)
• Σ2= {00,01,10,11} (22=4)
• Σ3= {000,001,010,011,100,101,110,111} (23= 8)
Strings
Kleene closure
• The set of strings over an alphabet Σ is usually denoted by Σ*
• For instance, Σ*= {0,1}* ={ ε,0,1,00,01,10,11,………}
• Therefore, Σ*= Σ0U Σ1U Σ2U Σ3…………. with ε symbol
Strings
Kleene plus (Positive closure)
• The set of strings over an alphabet Σ excluding ε is usually denoted by Σ+
• For instance, Σ+={0,1}+ ={0,1,00,10,01,11,…………}
• Therefore, Σ+= Σ*- { ε}
Or
• Σ+= Σ1U Σ2U Σ3…………. Without ε symbol
Strings
Prefix
• Removing zero or more trailing symbols
• w = 101 ; [1, 10, 101 ]

Suffix
• Removing zero or more leading symbols
• w = 101 ; [1, 01, 101 ]

Substring
• Eg w = 101
• 0, 01, 10 are substring
• 11 not a string
Concatenation of Strings

• Let x and y be strings. Then xy denotes the concatenation of x and y, that is, the
string formed by making a copy of x and following it by a copy of y.
• More precisely, if x is the string composed of i symbols
x = a1 a2…..ai and
• y is the string composed of j symbols
y = bi b2….bj,
• then xy is the string of length
i + j:
xy = a1a2…aib1b2…..bj.
Concatenation of Strings
Example
• Let x = 01101 and y = 110.
• Then xy = 01101110 and yx = 11001101.
• For any string w, the equations εw = wε = w hold.
• That is, ε is the identity for concatenation, since when concatenated with any
string it yields the other string as a result.
Languages

• A set of strings all of which are chosen from some Σ*, where Σ is a particular
alphabet, is called a language.
• If Σ is an alphabet, and L ⊆ Σ *, then Lis a language over Σ .
• Notice that a language over Σ need not include strings with all the symbols of Σ ,
so once we have established that L is a language over Σ , we also know it is a
language over any alphabet that is a superset of Σ .
Languages
1. The language of all strings consisting of n 0's followed by n l's, for some n >= 0:
{ε,01,0011,000111, ... }.
2. The set of strings of 0's and 1's with an equal number of each: {ε, 01, 10, 0011, 0101, 1001, ... }
3. The set of binary numbers whose value is a prime: {10,11,101,111,1011, .. }
4. Σ* is a language for any alphabet Σ.
5. Ø, the empty language, is a language over any alphabet.
6. {ε}, the language consisting of only the empty string, is also a language over any alphabet. Notice
that Ø ≠ {ε} the former has no strings and the latter has one string.
Language
L = {x01y | x and y are any strings of 0’s and 1’s }

Ans: 01, 11010, and 100011

Deterministic Finite
Automata
Deterministic Finite Automata, DFA
• The term "deterministic" refers to the fact that on each input there is
one and only one state to which the automaton can transition from its
current state.
Deterministic Finite Automata, DFA
A deterministic finite automaton consists of:
1. A finite set of states, often denoted Q.
2. A finite set of input symbols, often denoted Σ.
3. A transition function that takes as arguments a state and an input symbol and
returns a state. The transition function will commonly be denoted δ.
δ: Q × Σ → Q
1. A start state, one of the states in Q.
2. A set of final or accepting states F. The set F is a subset of Q.
Definition
“five-tuple” notation:
A= (Q, Σ, δ,q0,F)
where
• A is the name of the DFA,
• Q is its set of states,
• Σ its input symbols,
• δ its transition function, δ: Q × Σ → Q
• q0 its start state, and q0 ∈ Q
• F its set of accepting states, F ⊆ Q
Notations

1. Transition diagram,
2. Transition table
Transition diagram
A transition diagram for a DFA A= (Q, Σ, δ,q0,F) is a graph defined as follows:
a) For each state in Q there is a node.
b) For each state q in Q and each input symbol a in Σ , let δ(q,a) = p. Then the transition diagram
has an arc from node q to node p, labeled a. If there are several input symbols that cause
transitions from q to p, then the transition diagram can have one arc, labeled by the list of these
symbols.
c) There is a single start state in a DFA.
d) Nodes corresponding to accepting states (those in F) are marked by a double circle. States not in
F have a single circle.
Transition diagram
Start state

Final state

States

a
q0 q1
Transition
Transition Table
• A transition table is a conventional tabular representation of a function like δ that
takes two arguments and returns a value.
• The rows of the table correspond to the states, and the columns correspond to the
inputs.
• The entry for the row corresponding to state q and the column corresponding to
input a is the state δ(q, a).
The language accepted by DFA
• We need to understand about a DFA is how the DFA decides whether or not to "accept" a sequence
of input symbols.
• The "language" of the DFA is the set of all strings that the DFA accepts.
• Suppose a1a2 ….. an is a sequence of input symbols. We start out with the DFA in its start state, q0.
• We consult the transition function δ, say δ(q0,a1) = q1 to find the state that the DFA A enters after
processing the first input symbol a1
• We process the next input symbol, a2, by evaluating δ(q1, a2); let us suppose this state is q2
• We continue in this manner, finding states q3,q4, ...qn such that δ(qi-1,ai) = qi for each i.
• If qn is a member of F, then the input a1a2 ….. an is accepted, and if not then it is "rejected."
The language of DFA
• This language is denoted L(A), and is defined by
L(A) = {w | δ(q0,w) is in F}
• That is, the language of A is the set of strings w that take the start state q0 to one of
the accepting states.
• If L is L(A) for some DFA A, then we say L is a regular language.
DFA Problems
The language accepted by DFA
• We need to understand about a DFA is how the DFA decides whether or not to "accept" a sequence
of input symbols.
• The "language" of the DFA is the set of all strings that the DFA accepts.
• Suppose a1a2 ….. an is a sequence of input symbols. We start out with the DFA in its start state, q0.
• We consult the transition function δ, say δ(q0,a1) = q1 to find the state that the DFA A enters after
processing the first input symbol a1
• We process the next input symbol, a2, by evaluating δ(q1, a2); let us suppose this state is q2
• We continue in this manner, finding states q3,q4, ...qn such that δ(qi-1,ai) = qi for each i.
• If qn is a member of F, then the input a1a2 ….. an is accepted, and if not then it is "rejected."
The language of DFA
• This language is denoted L(A), and is defined by
L(A) = {w | δ(q0,w) is in F}
• That is, the language of A is the set of strings w that take the start state q0 to one of
the accepting states.
• If L is L(A) for some DFA A, then we say L is a regular language.
Extended transition function
• The extended transition function is a function that takes a state q and a string w
and returns a state p - the state that the automaton reaches when starting in
state q and processing the sequence of inputs w.
DFA - Problems
• Define a DFA which accepts the language L defined over {a, b} which
has string of length at least 3.
• Draw the transition diagram and construct the transition table
DFA - Problems
• Define a DFA which accepts the language L defined over {a, b} which
has string of length exactly 3.
• Draw the transition diagram and construct the transition table
DFA - Problems
• Define a DFA which accepts the language L defined over {0, 1} which
contain substring 01.
• Draw the transition diagram and construct the transition table
DFA - Problems
• Design a DFA for the language L = { an | n >= 0 } defined over a.
• Draw the transition diagram and construct the transition table
DFA - Problems
• Define a DFA accepts the language L = {w |w has both even number
of 0’s and even number of 1’s}
Extended transition function
• The input is 110101
• The check involves computing for each prefix w of 110101,
starting at ε and going in increasing size
Non-deterministic Finite
Automata
Nondeterministic Finite Automata
• Like the DFA, an NFA has a finite set of states, a finite set of input symbols, one
start state and a set of accepting states.
• It also has a transition function, called δ.
• The difference between the DFA and the NFA is in the type of δ.
• For the NFA, δ is a function that takes a state and input symbol as arguments like
the DFA's transition function, but returns rather than returning exactly one state,
as the DFA must.
Definition Nondeterministic Finite Automata
A nondeterministic finite automaton consists of:
1. A finite set of states, often denoted Q.
2. A finite set of input symbols, often denoted Σ.
3. A transition function that takes as arguments a state and an input
symbol and returns a set of zero, one, or more states . The transition
function will commonly be denoted δ.
δ: Q × Σ → 2Q
1. A start state, one of the states in Q.
2. A set of final or accepting states F. The set F is a subset of Q.
Definition Nondeterministic Finite Automata
“five-tuple” notation:
A= (Q, Σ, δ,q0,F)
where
• A is the name of the DFA,
• Q is its set of states,
• Σ its input symbols,
• δ its transition function, δ: Q × Σ → 2Q
• q0 its start state, and q0 ∈ Q
• F its set of accepting states, F ⊆ Q
Definition Nondeterministic Finite Automata
• Notice that transition tables can be used to specify the transition function for an
NFA as well as for a DFA.
• The only difference is that each entry in the table for the NFA is a set, even if the
set is a singleton (has one member).
• Also notice that when there is no transition at all from a given state on a given
input symbol, the proper entry is Ø, the empty set.
Difference between NFA and DFA
• NFA requires less space in comparison to DFA.
• NFA can use the Empty String transition, but DFA cannot use it.
• DFA is difficult to construct, whereas NFA is easy to construct.
• NFA stands for “Non-Deterministic Automata,” whereas DFA stands for
“Deterministic Automata.”
• NFA allows for multiple possible following states based on the current input. In
contrast, DFA has a unique transition from each state to every input.
• NFAs structure can be described as multiple little machines computing
simultaneously. Whereas the DFAs structure can be described as a single
machine.
• The number related to the next state can be one or zero in the case of NFA.
Whereas the number related to the following (next) state is one in the case of
DFA.
The language of NFA
• This language is denoted L(A), and is defined by

• That is, the language of L(A) is the set of strings w in Σ* such contains at
least one accepting states.
• If L is L(A) for some NFA A, then we say L is a regular language.
NFA - Problems
• Designing an NFA for the language containing substring 00.
NFA - Problems
• Transition Table
NFA - Problems
Check whether the string 001 is acceptable by the NFA or not
Equivalence of NFA and DFA
• Two machines are equivalent if they recognise the same language.

• All DFA are NFA. Not all NFA are DFA.

• The method used for conversion is called subset construction.

Subset Construction
Q1) Construct a DFA for the given NFA
Subset Construction
Step 1 : Construct the transition table for NFA

a b

q0 {q0, q1} {q0}

q1 {q1} { q2}

* q2 {q2} {q2}
Subset Construction
Step 2 :Construct transition table for DFA
1. In RHS if there is a new combination state take it as a new state.
new state  {q0, q1}
2. To find the transition use UNION
δ({q0, q1} , a) = δ(q0 , a) U δ(q1 , a) = {q0, q1}
δ({q0, q1} , b) = δ(q0 , b) U δ(q1 , b) = {q0, q2}
3. If a combination has a final state then that can be taken as final state in DFA.
{q0, q2} and {q0, q1 , q2} are final states
Subset Construction
a b

q0 {q0, q1} {q0}

{q0, q1} {q0, q1} {q0, q2}

* {q0, q2} {q0, q1, q2} {q0, q2}

* {q0, q1, q2} {q0, q1, q2} {q0, q2}

Subset Construction
Step 3 : Draw the DFA transition diagram from the transition table
Subset Construction
Q2) Construct a DFA from NFA in which all the states ends with 01
Sol : The NFA is
Subset Construction
NFA transition table

0 1

q0 {q0, q1} {q0}

q1 Ø { q2}

* q2 Ø Ø
Subset Construction
DFA transition table
0 1

q0 {q0, q1} {q0}

{q0, q1} {q0, q1} {q0, q2}

* {q0, q2} {q0, q1} {q0}

Subset Construction
DFA transition diagram
Finite Automata with epsilon
transition
Finite Automata with epsilon transition
• Allow a transition on ε, the empty string
• An NFA is allowed to make a transition spontaneously, without receiving an input
symbol
• Called ε - NFA
Definition ε - NFA
An ε - nondeterministic finite automaton consists of:
1. A finite set of states, often denoted Q.
2. A finite set of input symbols, often denoted Σ.
3. A transition function that takes as arguments a state and an input
symbol along with ε and returns a set of zero, one, or more states .
The transition function will commonly be denoted δ.
δ: Q × Σ U {ε} → 2Q
1. A start state, one of the states in Q.
2. A set of final or accepting states F. The set F is a subset of Q.
Definition ε-Nondeterministic Finite
Automata
“five-tuple” (quintuple)notation:
A= (Q, Σ, δ,q0,F)
where
• A is the name of the ε - NFA,
• Q is its set of states,
• Σ its input symbols,
• δ its transition function, δ: Q × Σ U {ε} → 2Q
• q0 its start state, and q0 ∈ Q
• F its set of accepting states, F ⊆ Q
The transition function of ε- NFA
• The transition function in ε-NFA contains
1. A state in Q, and
2. A member of Σ U {ε} that is, either an input symbol, or the symbol ε. ε, the
symbol for the empty string, cannot be a member of the alphabet Σ.
ε- NFA Example
Eg:

Fig. 1
• ε- NFA = NFA
• Every state on ε goes to itself.
• ie δ(q0, ε) = q0, δ(q1, ε) = q1 and so on..
Epsilon Closure
• ε- closure, denoted as ε*
• All the states that can be reached from a particular state only by
seeing the ε symbol.
• Otherwise denoted as ECLOSE().
• ECLOSE() a state q by following all transitions out of q that are
labelled ε.
• However, when we get to other state by following ε, we follows the
ε- transitions out of those states, and so on, eventually finding every
state that can be reached from q along any path whose arcs are all
labelled ε.
ε- closure
• ε- closure of Fig 1
ε- closure(q0) = {q0, q1, q2} ECLOSE(q0) = {q0, q1, q2}

ε- closure(q1) = {q1, q2} OR ECLOSE(q1) = {q1, q2}

ε- closure(q2) = {q2} ECLOSE(q2) = {q2}

ε- NFA to NFA
• Convert the following ε- NFA to NFA
ε- NFA to NFA
Sol:

State ε* Input Symbol ε*

Input -- 0

q0 q0 q0 q0
q1
q2
q1 Φ Φ
q2 q2 q2
δ(q0, 0) = {q0, q1, q2}
ε- NFA to NFA
State ε* Input Symbol ε*

Input – 1

q0 q0 Φ Φ
q1 q1 q1
q2
q2 q2 q2

δ(q0, 1) = {q1, q2}

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q1 q1 Φ Φ
q2 q2 q2

Input - 1
q1 q1 q1 q1
q2 q2
q2 q2

δ(q1, 0) = {q2} and δ(q1, 1) = {q1, q2}

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q2 q2 q2 q2

Input - 1

q2 q2 q2 q2

δ(q2, 0) = {q2} and δ(q2, 1) = {q2}

ε- NFA to NFA
• Transition Table

o 1

*q0 {q0, q1, q2} {q1, q2}

*q1 {q2} {q1, q2}

*q2 {q2} {q2}

ε- NFA to NFA
• Transition Diagram
ε- NFA to NFA – Problem 2
• Convert the following ε- NFA to NFA
ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q0 q0 Φ Φ
q2 q3 q3

Input - 1

q0 q0 q1 q1
q2 q4 q4

δ(q0, 0) = {q3} and δ(q0, 1) = {q1, q4}

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q1 q1 Φ Φ

Input - 1

q1 q1 q0 q0

q2

δ(q1, 0) = Φ and δ(q1, 1) = {q0, q2}

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q2 q2 q3 q3

Input - 1

q2 q2 q4 q4

δ(q2, 0) = {q3} and δ(q2, 1) = {q4}

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q3 q3 q2 q2

Input - 1

q3 q3 Φ Φ

δ(q3, 0) = {q2} and δ(q3, 1) = Φ

ε- NFA to NFA
State ε* Input Symbol ε*

Input - 0
q4 q4 q2 q2

Input - 1

q4 q4 Φ Φ

δ(q4, 0) = {q2} and δ(q4, 1) = Φ

ε- NFA to NFA
• Transition Table
o 1

*q0 {q3} {q1, q4}

q1 Φ {q0, q2}

*q2 {q3} {q4}

q3 {q2} Φ

q4 {q2} Φ
ε- NFA to NFA
• Transition Diagram
Steps for converting ε NFA to DFA
1. Take the ε-closure for the starting state of ε NFA as a starting state
of DFA.
2. Find the states for each input symbol that can be traversed from the
present. That means the union of transition value and their closures
for each state of ε NFA present in the current state of DFA.
3. If we found a new state, take it as current state and repeat step 2.
4. Repeat Step 2 and Step 3 until there is no new state present in the
transition table of DFA.
5. Mark the states of DFA as a final state which contains the final state
of ε NFA.
ε-NFA to DFA – Example 1
• Convert the following ε NFA to DFA
ε-NFA to DFA
• Transition table for ε-NFA
a b c ε

q0 {q0 } Φ Φ {q0, q1 }

q1 Φ {q1} Φ {q1, q2 }

*q2 Φ Φ {q2 } {q2 }

ε-NFA to DFA
• Transition table for DFA
a b c

*{q0, q1, q2 } {q0, q1, q2 } {q1, q2 } {q2 }

*{q1, q2 } Φ { q1, q2} {q2 }

*q2 Φ Φ {q2 }
ε-NFA to DFA
• Renaming

• Let A  {q0, q1, q2 }

• B  {q1, q2 }
• C  {q2 }
• D  Trap State

• Transition Diagram
ε-NFA to DFA – Problem 2
• Convert the given ε-NFA to DFA
ε-NFA to DFA
Let us obtain ε-closure of each state.
• ε-closure {q0} = {q0, q1, q2}
• ε-closure {q1} = {q1}
• ε-closure {q2} = {q2}
• ε-closure {q3} = {q3}
• ε-closure {q4} = {q4}
• Now, let ε-closure {q0} = {q0, q1, q2}
ε-NFA to DFA
• Transition table for DFA
0 1

{q0, q1, q2 } {q3 } {q3 }

{q3} Φ { q4}

*q4 Φ Φ
ε-NFA to DFA
• Renaming

• Let A  {q0, q1, q2 }

• B  {q3 }
• C  {q4 }
• D  Trap State

• Transition Diagram
ε-NFA to DFA – Problem 3
• Convert the given ε-NFA to DFA
ε-NFA to DFA
Let us obtain ε-closure of each state.
• ε-closure(q0) = {q0, q1, q2}
• ε-closure(q1) = {q1, q2}
• ε-closure(q2) = {q2}

• Now, let ε-closure {q0} = {q0, q1, q2}

ε-NFA to DFA
• Transition table for DFA
0 1 2

*{q0, q1, q2 } {q0, q1, q2 } {q1, q2} {q2}

*{q1, q2} Φ {q1, q2} {q2}

*{q2} Φ Φ {q2}
ε-NFA to DFA
• Renaming

• Let A  {q0, q1, q2 }

• B  {q1, q2 }
• C  {q2 }
• D  Trap State

• Transition Diagram
Minimization of DFA
Minimization of DFA
• Minimization of DFA means reducing the number of states from given
FA. Thus, we get the FSM(finite state machine) with redundant states
after minimizing the FSM.
• The steps are
1. Remove all the states that are unreachable from the initial state via any set
of the transition of DFA.
2. Draw the transition table for all pair of states.
3. Now split the transition table into two tables T1 and T2. T1 contains all final
states, and T2 contains non-final states.
Minimization of DFA
4. Find similar rows from T1 such that:
δ (q, a) = p
δ (r, a) = p
That means, find the two states which have the same value of a and b and
remove one of them.
5. Repeat step 3 until we find no similar rows available in the transition table
T1.
6. Repeat step 3 and step 4 for table T2 also.
7. Now combine the reduced T1 and T2 tables. The combined transition table
is the transition table of minimized DFA.
Problem 1
Minimize the following DFA
Solution
1. In the given DFA, q2 and q4 are the unreachable states so remove
them.
2. Draw the transition table for the rest of the states.
Solution
3. Now divide rows of transition table into two sets as:
• One set contains those rows, which start from non-final states:

• Another set contains those rows, which starts from final states.
Solution
4. Set 1 has no similar rows so set 1 will be the same.

5. In set 2, row 1 and row 2 are similar since q3 and q5 transit to the
same state on 0 and 1. So skip q5 and then replace q5 by q3 in the
rest.
Solution
6. Now combine set 1 and set 2 as:

Now it is the transition table of minimized DFA.

Solution
The minimized DFA is
Problem 2
• Minimize the given DFA
Solution
• The minimized DFA is
Regular Grammar
Grammar
• A grammar is a language generator
• Formally defined as quadruples or 4 tuples
G = (V, T, P, S)
• V – finite non empty set of non terminals or variables, generally
written in upper case letters
• T – finite non empty set of terminals, generally written in lower case
letters.
• P – set of production rules
• S – start symbol, S ∈ V
Grammar
• The production are of the form
αβ
Where α contains single non terminal. ie, single non terminal on the
left hand side.
β can be a combination of terminals and non terminals
Regular Grammar
• Also known as Type 3 grammar
• A grammar is said to be regular, if it is either right linear or left linear.
• Regular grammar generates regular language.
• Formally a regular grammar is defined by a quadruple (V, T, P, S)
• Where V – finite non empty set of non terminals or variables, generally
written in upper case letters
• T – finite non empty set of terminals, generally written in lower case
letters.
• P – set of production rules
• S – start symbol, S ∈ V
Regular Grammar
• The production rules are defined as
αβ
and production are of the form:
1. Right Linear 2. Left Linear
A  aB A  Ba
Aa Aa
Aε Aε
Where A ∈ V Where A ∈ V
a∈T a∈T
Regular Grammar
Consider a production
S  aS
Sε
This is generally written as
S  aS | ε
This is right linear and the derivation of string “aaaa” from the grammar is as follows
S  aS
S  aaS
S  aaaS
S  aaaaS
S  aaaa ε
S  aaaa
Regular Grammar
• This is the language
L = { an | n >= 0}
And the finite automata is
a

q0
Conversion of regular grammar to finite
automata
1. Construct an ε free regular grammar (grammar without ε production, A
 ε is called ε- production) G’ from G.
2. Create an FSA ‘M’ with state for every non terminal in G’. Set the state
representing the start symbol in G’ as the start state.
3. Add another new state qf as final state.
4. For every production of the form A  aB, add a transition from state A to
state B on input signal ‘a’.
5. For every production A  a, add a transition from state A to the final
state.
6. If there is a production S  ε in G’, where S is the start symbol in G’,
make S as a final state.
Removing ε production/ Creating ε free
grammar
A regular grammar is said to be ε free, if it has no ε productions except
possibly for the production S  ε, where S is the start symbol and S
does not appear on the right hand side of any production.
The steps are:
1. Copy all non ε productions from G to G’.
2. For any non terminal N which can become ε (ie, N  ε), copy every
rule in which N appears on the RHS both with and without N.
3. If S  ε was in the original set of rules, add a new start symbol S’ in
G’ and add the production S’  ε and copy all the production rules
of S to the RHS of S’.
Examples – Problem 1
1. Construct a finite state automata for the regular grammar.
S  a | aA | bB | ε
A  aA | aS
B  cS | ε
Solution
The ε production in the given grammar are S  ε and B  ε
So, substitute these two production in the RHS of all the production containing S
and B.
First we can choose S  ε.
S is appeared in RHS of two productions A  aS and B  cS
Substituting S  ε, we get A  a. ε and B  c. ε
ie, A  a and B  c
So, the complete production becomes
S  a | aA | bB
A  aA | aS | a
B  cS | c
Solution
Now consider B  ε. B is appeared in RHS of only one production
SbB.
So, the production become S  b.
Then the productions become
S  a | aA | bB | b
A  aA | aS | a
B  cS | c
Since the original grammar contains S  ε, we can make a new start
symbol S’
Solution
Then the complete production becomes
S’  a | aA | bB | b | ε
S  a | aA | bB | b
A  aA | aS | a
B  cS | c

Fig : FSA of RG
Problems
Construct FSA for the given RG
1. S -> aA | bC | ε
A -> aA | aS
B -> b
C -> cB | cS
2. S -> aA | bC
A -> aA | bB | ε
B -> bB | b |ε
C -> cB | bC | ε
Conversion of FSA to RG
1. Begin from start state
2. For every transition δ(Q, a) = P
add production Q  aP
3. For every Q ∈ F,
add a production Q  ε
Problem 1
• Convert FSA to RG
Solution
• The transitions from the FSA are
δ(A, a) = B : A  aB
δ(B, a) = B : B  aB
δ(B, b) = B : B  bB
B∈F : Bε
Hence, the complete production are
A  aB
B  aB | bB | ε
Problem 2
• Convert the FSA to RG
Solution
δ(A, a) = B : A  aB
δ(A, b) = A : A  bA
δ(B, a) = C : B  aC
δ(B, b) = B : B  bB
δ(C, a) = A : C  aA
δ(C, a) = D : C  aD
δ(C, b) = C : C  bC
D∈F : Dε
Solution
Then the production are
A  aB | bA
B  aC | bB
C  aD | aA | bC
Dε
Problem 3
• Convert the FSA to RG
Solution
δ(q0 , 0) = q1 : q0  0q1
δ(q0 , 1) = q3 : q0  1q3
δ(q1 , 0) = q0 : q1  0q0
δ(q1 , 1) = q2 : q1  1q2
δ(q2 , 0) = q3 : q2  0q3
δ(q2 , 1) = q1 : q2  1q1
δ(q3 , 0) = q2 : q3  0q2
δ(q3 , 1) = q0 : q3  1q0
q0 ∈ F : q0  ε
Solution
q0  0q1 | 1q3 | ε
q1  0q0 | 1q2
q2  0q3 |1q1
q3  0q2 | 1q0