Session 3: An Informal Picture of Finite Automata, finite automaton model, acceptance of strings, and

languages
1. Course Description

The course introduces on fundamental concepts of Computer science and formal methods of
computation like automata theory and formal languages including grammar, finite automaton, regular
expression, formal language, pushdown automaton, and Turing machine. Not only do they form basic
models of computation, they are also the foundation of many branches of computer science, e.g.
compilers, software engineering, concurrent systems, etc. The properties of these models will be
studied and various rigorous techniques for analyzing and comparing them will be discussed, by using
both formalism and examples.
2. Aim
 Study various automata, such as deterministic and nondeterministic finite-state machines,
pushdown automata, and Turing machines.
 Study formal languages of different kinds, such as regular and context-free languages.
 Understand the connections between languages and automata, and related algorithms for
transformations.
 Understand the basic results on computability, including undecidable problems such as the halting
and Post correspondence problems, and their significance.
 Study the basics of intractability, including NP-completeness and related topics.
 Make connections between theoretical results and topics in practical software development, such
as finite automata and regular-expression libraries.
 Improve programming skills, with emphasis on connections between theoretical results and
practical software.
3. Instructional Objectives

The objective of this course is to classify machines by their power to recognize languages and
comprehend the hierarchy of problems arising in the computer sciences
4. Learning Outcomes
 Make use of Finite State Machines for Modeling and Solving computing problems for different
languages
 Construct regular expressions for different languages
 Model Push Down Automata for CFLs and constructs a PDA for different CFLs
 Make use of Context-Free languages and Turing Machines for different unrestricted languages
5. Module Description

CO1: Introducing the concepts of automata theory Understand NFA and DFA Conversions and Equivalence of
Different finite automata
CO2: Introducing the concepts of Regular Languages Understand Pumping lemma of regular sets, closure
properties of regular sets Equivalence between regular linear grammar and FA, interconversion.
CO3: Introducing the concepts of Context-Free Grammars Understanding Chomsky Normal Form (CNF) and
Greibach Normal Form (GNF) Push down automata model and its equivalence
CO4: Introducing the concepts of Types of PDA Understand Turing Machine Concepts Counter machine and
Restricted Turing Machines
Session Introduction:

Finite Automata(FA) is the simplest machine to recognize patterns. The finite automata or finite state
machine is an abstract machine that has five elements or tuples. It has a set of states and rules for
moving from one state to another but it depends upon the applied input symbol.
Session Description:
Finite Automata is mainly classified into two types

1. Deterministic Finite Automata (DFA) : There is exactly one transition from each input symbol
2. Non Deterministic Finite Automata (NFA): There are Zero, one or more transitions from each input
symbol (There may not be transition for an input symbol)

Non Deterministic finite automata (NFA):

Definition: A NFA is a 5-tuple M = (Q, ∑, q0, F, δ) Where Q

: is a finite set of states

∑ : is a finite input alphabet

q0 : is a initial state, q0 ∈ Q

F : is a set of final states, F ⊆ Q

δ is a transition mapping function from Current state to

next state depending on the input.
δ: Q × Σ → 2Q
Note: A NFA consists of a finite set of states and set of transitions from state to state.
For each input symbol there are zero, one or more transitions.
Example: Design NFA for the following using the above representation:

L={w|w contain either ‘00’ or ‘11’}

L={00,11,000,111,001,110, …….}

4. Construct DFA, L={w|w conatains even number of ‘0’s’ and even number
of ‘1’s ,∑={0,1}}

L={0011,1010,1100,0101,..................}
5. Construct DFA , L={w|w conatains even number of a’s, ∑={a,b}}
L={ε,aa,b,baa,aab,aba,bbaa,.............}

6. Construct DFA, L={w|w conatains odd number of b’s, ∑={a,b}}

L={ε,b,bbb,abb,aabbb,.......................}
7. Construct DFA, L={w/w represent base 3 divisible by 4}
L={0,11,22,….}
Note: Decimal number convert into Base3

8. Construct DFA, L={w/|w| <=4 w={a,b}}

L={ε,a,b,aaa,bab,aa,a,bbb,abab….}
9. Construct DFA, L={w/w contains b as a third symbol from right w={a,b}}

L={bab,ababaa,babbb,bbb,bbab,aabab….}

10.Construct DFA, L={w/w contains a as a second symbol from left w={a,b}}

L={ ba,aaaa,aabb,aaab…..}
11. Design a DFA which accepts set of strings that does not contain “010” as
substring over an alphabet ∑ = {0, 1}.

Step 1: Creating the DFA that contains “010” as substring

L = {010, 1010, 0101, 0010...}

Step 2: Creating the DFA that does not contains “010” as substring

L = {ε, 10, 110, 101, 000...}

12.Design a DFA which accepts set of strings that starts and ends with ‘b’
(same symbol) over an alphabet ∑ = {a, b}.

L = {ε, a, b, aa, bb, aba, bab, ababa, aabba, aaabbba,...}

13.L = {w / |w| = 3 and w starts with ‘a’} over an alphabet ∑ = {a, b}.

L = {aaa, aab, abb, aba,...}

6. Activities
1.Design the DFA for the following Languages and complete the Cross word Puzzle given below
1. L={w| w starts with ‘a’ where ∑={a,b} }

2. L={w| |w|=2 over input alphabet ∑={a,b,c} ; |w| indicates length of string}

3. L={w| w contains atmost 1 ‘a’ only where ∑={a,b} }

4. L={w| |w| mod 5 !=0 over input alphabet ∑={a, b} ; |w| indicates length of string; ‘mod’ gives
remainder}

5. L={w| w contains exactly two 0’s over input alphabet ∑={0, 1} }

6. L={w| w contains ‘11’ as a substring where ∑={0, 1} }

2.

3. Design the PDAs for the following Languages and complete the Cross word Puzzle given below
n n m m
1. L={a b c d | n>0,m>0 }
2. L={language of balanced parenthesis eg: (())()() }
3. L={w| w contains equal number of a’s and b’s where ∑={a,b} }

7. Examples

1. Design NFA for the following languages: a) L={w/w contains three consecutive one’s } Σ={0,1} b)
L={w/w contains exactly two occurances of ‘00’ } Σ={0,1} c) L={xЄ{a,b,c}* / x contains exactly one ‘b’
immediately followed by ‘c’} Σ={a,b,c} d) L={w/w contains mod 5 not equal to 0 } Σ={a,b}
2. Convert the following NFA to DFA
 a)

b)

c)

3. Represent Regular expression for the following language

a) Strings of 0’s and 1’s containing odd number of 1’s or even number of 0’s over {0,1}.
b) Set of strings of 0’s and 1’s of length less than 6 over {0,1}.
c) Set of strings of 0’s and 1’s that ends with 1 and does not contain substring 00 over {0,1}.
d) Set of strings of a’s and b’s that begins and ends with same symbol over {a,b}.
e) The language of all strings 0’s and 1’s in which every 0 is followed immediately by 11 over {0,1}.
f) The language of all string containing atleast two 0’s over {0,1}.
g) The language of all strings that do not end with 01 over {0,1}.
4. The following languages are regular or not. Justify the answer.
a) L = { 0n102n |n>=0}
b) L = { 0i1j| j = i or j = 2i }
c) L = { a2nb3m | n>=1, m>=1}
d) L = { 0i1j | j is a multiple of i }
e) L = { xy | x,y ϵ { 0, 1}* and y is either x or x r }
5. Minimize the DFA shown below.
8. Self-Assessment Questions

1. Applications of Finite Automata

2. Give examples of Graphs
3. Represent a Language “All even numbers” in two ‘Set’ formats
4. Differentiate between Tree and Graph
5. How many ways we can represent finite automata and what are they?
6. What are the components of Finite Automaton
7. Transition In FA can be either Left to Right or Right to Left (TRUE/FALSE)
8. Differentiate between Start and Final states
9. Define M for DFA
10. What is the importance of dead state
11. Transitions of Finite Automata can be represented in 2 ways only (TRUE/FALSE)
12. How F is related to Q in DFA
13. How do you decide the number of states in a DFA
14. Describe the meaning of ‘Deterministic’ in DFA
15. Define the M for the following Sate Diagram

16. Explain how transition function mapped in DFA

17. Design DFA for the Language L={w/w starts with 11 or 00 over {0,1}
18. Write the transition function for the above DFA
19. Denote the Five tuple notation for the above DFA
20. Is the following Automation is DFA (YES/NO). Justify

21. Define NFA?

22. Differentiate between NFA and DFA?
23. Explain the mapping function of NFA
24. Mention whether the State Diagram is NFA or DFA. Justify
 25. Design NFA for the Language L= {w/w does not contain substring ‘010’ over alphabet {0,1} }
26. Write the transition function for the above NFA
27. Denote the Five tuple notation for the above NFA
28. Is the following Automation is NFA (YES/NO). Justify

29. NFA is more powerful than DFA (TRUE/FALSE). Justify

30. What is the equivalence of NFA and DFA
31. For every NFA there exist a DFA (YES/NO)
32. Which automaton (NFA or DFA) is easy to design and why?
33. Define ε-transition in NFA
34. Can DFA have ε-moves
35. Is Every FA with Epsilon move an NFA
36. Which is more powerful (DFA/NFA/ ε-NFA). Justify
37. What is meant by Epsilon closure
38. Differentiate between Extended 𝛿 and 𝛿 functions
39. Every ε-NFA has equivalent DFA (TRUE/FALSE). Justify
40. Design ε-NFA for L={ a^n b^m / n,m >=0}

1. If there are two sets A and B , then their intersection is denoted by [ ]

A) A B B) A B C) A + B D) none of these.
2. A relation R is said to be , if for two elements ‘a’ and ‘b’ in X, if a is related to b then b is
related to a. [ ]
A) Symmetric B) Transitive C) equivalence relation D) none of these.
3. A relation R is said to be relation on A , if R is reflexive, symmetric and transitive. [ ]
A) Equivalence Relation B) Non-Equivalence Relation C) Relation D) none of these.
4. A Grammar consists of tuples . [ ]
A) Four B) Five C) Three D) None of these.
5. In the following which one is correct [ ]
A) a+=a*.a* B) a*=a+.a C) a+=a*.a D) None of these
6. Which of the following grammar generates strings with any number of 1’s [ ]
A) S 1A, Aε B) S 1S, Sε C) SS0, S ε D) None of these.
7. Grammar consists of four tuples such as set of non terminals, , set of production rules
and . [ ]
A) Set of terminals B) Start symbol C) A & B D) None of these.
8. Type 1 grammar is called [ ]
A) Regular Grammar B) Context free grammar
C) Context sensitive language. D) None of these
9. According to the Chomsky Hierarchy, regular grammar is Type grammar. [ ]
A) 0 B) 1 C) 2 D) 3
10. Which is correct for δ(q,ab) [ ]
A) δ(q,a) δ(q,b) B) δ(δ(q,a),b) C) δ(q,a),b D) None of these.
11. The maximum number of state of a DFA converted from an NFA with n states is [ ]
A) n B) n2 C) 2n D) none of these.
12. Which is true for the Mealy Machine? [ ]
A) Output depends on the present state. B) Output depends on the present input.
C) Output depends on the present state and the present inputs. D) None of these.
13. Finite automata is defined as [ ]
A) M={Q,∑,δ,q0,F} B)M={Q,∑,q0,F} C) M={Q,δ,q0,F} D) none of these
14. For DFA, the transitional function δ is representing by Q x ∑ [ ]
A) q0 B) F C) Q D) none of these.
15. In any finite automata contains any ε move, then that finite automata is called with ε moves.
A) NFA B) DFA C) A& B D) none of these [ ]
16. In the tabular format representation of finite automata, the single circle state representing state.
A) final B) starting C) intermediate D) none of these [ ]
17. A relation R in set S is , if for x,y and z in S, xRz wheneverxRy and yRz. [ ]
A) Symmetric B) Transitive C) equivalence relationD) none of these.
18. The Myhill- Nerode theorem is used for [ ]
A) Maximizing the FA B) Minimizing the FA C) both A & B D) none of these.
19. In the Moore Machine , the output depends on [ ]
A) Present state B) final state C) input symbol D) none of these
20. Type 2 language is called as _ [ ]
A) Regular Expression B) Context free grammar C) context sensitive language D) none of these.
 21. A language set contains [ ]
A) String B) Alphabet C) set D) none of these.
22. If ∑={1}, then ∑ *- ∑ + is [ ]
A) 1+ B) {1} C) {ε} D) none of these
23. 1+ means [ ]
A) Any combination of 1 including ε B) Any combination of 1 excluding ε
C) only once D) none of these
24. In a Grammar, are those symbols which can be replaced multiple times. [ ]

A) Terminal B) Non Terminal C) Start SymbolD) none of these.

25. A set having infinite number of elements is called . []
A) Set B) Finite set C) Infinite set D) None
26. An alphabet is a finite set of symbols then it is denoted by in automata. [ ]
A) ε B)∑ C) E D) none of these.
27. If 00000111 is a binary string then length of given string |w| is []
A) 4 B) 8 C) 5 D) none of these.
28. In a given grammar SaSAc/abc , Abb, the terminal symbols are [ ]
A) ab B) A C) S D) abc.
29. The finite automata with output can be divided into types. [ ]
A) 2 B) 3 C) 4 D) none of these.
30. For a Moore machine, the states are labeled with the in a transitional diagram [ ]
A) state name only B) output only C) state name and output D) none of these.
31. An Finite automata has a number of states. [ ]
A) Infinte B) finite C) only 5 D) none of these.
32. Which of the following string is of length 0? [ ]
A) s B) abc C) ab D) {ε}
33. In below fig Є-closure (q0) is [ ]
0 12
q0  q1  q2
A) {q0} B){q0,q1} C) {q0,q1,q2} D) {q0,q2}
34. The regular expression 1 + 0 1 = [ ]
A) ε + 0 B) ( ε + 0 ) 1 C) 1 01 D) 1 ( ε + 0 )

35. Consider the following finite automata. The regular expression for this FA is [
]
A)ε B) a C) aa D) a*
36. The union of two regular expressions R1 and R2, written as R1 + R2 is also a regular expression. [ ]
 A) True B)False C) True of False D) Can’t say
37. Let the input alphabet be ∑ = {0}, then ∑* = [ ] A) {ε}
B) {ε, 0} C) {0} D) {ε, 0, 00, 000, …….}
38. In transition diagram the final state is represented as [ ]
A) Single Circle B) Star C) Double Circle D)Arrow
39. The regular expression for the regular set { 2,22,222,........ } is . [ ]
A) 2* B) 2+ C) 2(2) * D) both (B) & (C)
40. DFA stands for [ ]
A) Deterministic Finite Authorization B) Deterministic Finite Acceptance
C) Deterministic Finite Automaton D) Deterministic Finite Analysis

9. Summary

Formal Languages and Automata Theory introduces you to the concepts associated languages, computation and
machines. It uses mathematical structure, and certain axiomatic rules (formal grammar) to describe translation of
programs written in computer languages. The notions and methods of formal language are analogous to those used
in number theory and in logic. This brought in latest developments in computer technology such as the recognition
neurons in artificial intelligence and robotic programming. The content of the course material was planned and
written to ensure that you acquire the proper knowledge and skills, Real-life situations have been created to enable
you identify with and create some of your own. The essence is to help you in acquiring the necessary knowledge
and competence by equipping you with the necessary tools to accomplish this.
10. Terminal Questions
1. A. Write about Finite Automata & String Acceptance
B. Design DFA for the following Language L= {x01y/ x and y are strings of 0’sand 1’s} Define all the elements of
DFA
C. Give an example of Transition Diagram and Transition Table of FA
2. A. Specify some applications of Finite Automata
B. State and Prove the Equivalence of NFA and DFA
C. Design an equivalent DFA from the following NFA, where the transition function of NFA is given by δ (q0,
0) = {q0, q3}, δ(q0,1)={q0,q1}, δ(q1,0)=Ф, δ(q1,1)= q2, δ(q2,0)=q2, δ(q2,1)=q2, δ(q3,0) =q4, δ(q3,1) =Ф,
δ(q4,0) =q4, δ(q4,1) =q4, q0 is an initial state and q2 & q4 are the final states.
3. A. Write Regular Expression for the following languages
i. Set of Strings that consists of alternate 0’s and 1’s
ii. Set of Strings of a's and b's that ends with 'ab' or 'bb'
iii. Set of strings of a's and b's that begins with 'ab' and contains the substring 'ba'
B. Design NFA with ε-transitions for the following Regular Expression
i. a (a+b)*a + b (a+b)*b ii. (0+1)*(00+11)
4. A. Minimize the following DFA, where q0 and q4 are the initial and final states respectively

State
q0 q1 q3
q1 q2 q4
q2 q1 q4
q3 q4 q2
q4 q4 q4
B. State and Prove any Three Closure Properties of Regular Sets
5. A. Define PDA (Push Down Automata). Give its Mathematical Representation
B. Design PDA for the following Language
L = {Set of Equal Number of 0's and 1's over {0, 1}}
C. When do you say that a CFG is Unambiguous? Is the following CFG ambiguous or not? Justify your answer
with an example with V = {S, E} T = {if, then else, other}, P, {S}
S  if E then S S  if E then S else S E  other
6. A. Define a. Useless symbol b. Null Production c. Unit Production
B. Find a Grammar equivalent to S AB/AC A
aA/bAa/a B bbA/aB/AB CaCa/aD D  aD/bC with no use less symbols
7. A. Define Turing Machine. Give its Mathematical Representation
B. Design Turing Machine for the following language. Represent all the elements
L = {Set of Equal number of a's and b's over {a, b}}
C. Define Recursively Enumerable Languages. Give any three examples
8. A. Define the following
i. CNF (Chomsky Normal Form) ii. GNF (Griebach Normal Form)
Find an equivalent grammar in CNF from the following CFG S ABa
A aab B Ac
B. Consider the following CFG
S AB/BC ABA/a BCC/b CAB/a
Find whether the given string 'baaba' is a part of the language generated by the CFG using CYK algorithm.
9. A. Design DFA for the set of all strings such that the third symbol from the right end is '1' over Σ = {0,1}.
Represent all the elements of DFA.
B. The following are two finite automata M1(Q1, {0,1}, q0, δ1, {q0, q1}) and M2(Q2, {0,1}, p0, δ2, {p2})
corresponding to regular languages L1 and L2 with the transition functions given below. For machine M1,
δ1(q0,0)=q1, δ1(q0,1)=q0, δ1(q1,0)=q2, δ1(q1,1)=q0, δ1(q2,0)=q2, δ1(q2,1)=q2, where q0 is an initial and a
final state and q2 is a final state respectively. For machine M2, δ2(p0,0)=p1, δ2(p0,1)=p0, δ2(p1,0)=p1,
δ2(p1,1)=p2, δ2(p2,0)=p1, δ2(p2,1)=p0. Here p0 is an initial state and p2 is a final state. Draw transition
diagram & transition table for M1 and M2
10. A. Differentiate between NFA & DFA
B. Design NFA for the language L={an U bn / n>=1}. Represent all the elements of NFA
C. Define NFA with ε- transitions and give its Mathematical Representation
11. References of books, Sites, Links

Text Books :
T1. John E. Hopcroft, Rajeev Motwani, and Jeffery D. Ullman, “Introduction to Automata Theory, Languages and
Computation”, 3rd Edition, Pearson Education, 2008.
T2. Linz, Peter, “An Introduction to Formal Languages and Automata”, Sixth Edition—2016,Jones and Bartlett.
Reference Books :
R1. Sipser J Michael, “Introduction to Theory of Computation”, Third Edition—2015, Cengage.
R2. Martin Jhon, “Introduction to Languages and Theory of Computation”, Third Edition—2016, PHI.
Web Links :
1. Theory Of Computation and Automata Tutorials: https://www.geeksforgeeks.org/theory-of- computation-
automata-tutorials/
2. Automata Tutorial: https://www.javatpoint.com/automata-tutorial
3. Automata Theory Tutorial: https://www.tutorialspoint.com/automata_theory/index.htm
4. Automata Tutorial: https://www.tutorialandexample.com/automata-tutorial

12. Keywords
NFA, DFA, Pushdown Automata, Pumping Lemma, Grammar, CFG, Turing Machine, Chomsky Hierarchy,
Derivation Keys.