Formal Language

and Automata
Theory

CS402
For
B.Tech CSE 2nd year Students

WORK BOOK

University of Engineering & Management, Kolkata

Code : CS402
Contacts : 3L+1T
Credits :4

Prerequisites of Formal Language & Automata Theory:

Elementary discrete mathematics including the notion of set, function, relation, product, partial order,
equivalence relation, graph & tree. They should have a thorough understanding of the principle of
mathematical induction.

Module – 1 :
Fundamentals: Basic definition of sequential circuit, block diagram, mathematical representation,
concept of transition table and transition diagram (Relating of Automata concept to sequential circuit
concept) Design of sequence detector, Introduction to finite state model.

Finite state machine: Definitions, capability & state equivalent, kth- equivalent concept, Merger graph,
Merger table, Compatibility graph, Finite memory definiteness, testing table & testing graph.
Deterministic finite automaton and non deterministic finite automaton. Transition diagrams and
Language recognizers.

Finite Automata: NFA with Î transitions - Significance, acceptance of languages. Conversions and
Equivalence: Equivalence between NFA with and without Î transitions. NFA to DFA conversion.
Minimization of FSM, Equivalence between two FSM’s , Limitations of FSM. Application of finite
automata, Finite Automata with output- Moore & Melay machine.

Learning outcome of Finite Automata:

The student will be able to define a system and recognize the behavior of a system. They will be able to
minimize a system and compare different systems.

Module – 2 :
Regular Languages : Regular sets. Regular expressions, identity rules. Arden’s theorem state and prove.
Constructing finite Automata for a given regular expressions, Regular string accepted by NFA/DFA.
Pumping lemma of regular sets. Closure properties of regular sets (proofs not required).

Grammar Formalism: Regular grammars-right linear and left linear grammars. Equivalence between
regular linear grammar and FA. Inter conversion, Context free grammar. Derivation trees, sentential
forms. Right most and leftmost derivation of strings. (Concept only)

Learning outcome of Regular Languages and Grammar:

Student will convert Finite Automata to regular expression. Students will be able to check equivalence
between regular linear grammar and FA.
Module – 3 :
Context Free Grammars, Ambiguity in context free grammars. Minimization of Context Free Grammars.
Chomsky normal form and Greibach normal form. Pumping Lemma for Context Free Languages.
Enumeration of properties of CFL (proofs omitted). Closure property of CFL, Ogden’s lemma & its
applications.

Push Down Automata:

Push down automata, definition. Acceptance of CFL, Acceptance by final state and acceptance by empty
state and its equivalence. Equivalence of CFL and PDA, interconversion. (Proofs not required).
Introduction to DCFL and DPDA.

Learning outcome of PDA and context free grammar:

Students will be able to minimize context free grammar. Student will be able to check equivalence of CFL
and PDA. They will be able to design Turing Machine.

Module – 4 :
Turing Machine : Turing Machine, definition, model. Design of TM, Computable functions. Church’s
hypothesis, counter machine. Types of Turing machines (proofs not required). Universal Turing Machine,
Halting problem.

Learning outcome of Turing Machine :

Students will be able to design Turing machine.
Module – 1:

1. Design a two input two output sequence detector which generates an output ‘1’ every time the
sequence 1001 is detected. And for all other cases output ‘0’ is generated. Overlapping
sequences are counted.
2. Design a two input two output sequence detector which generates an output ‘1’ every time the
sequence 1010 is detected. And for all other cases output ‘0’ is generated. Overlapping
sequences are counted.
3. Design a sequential circuit which performs following
A B O/P Carry
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
4. Design a full binary subtractor.
5. What do you mean by finite state machine?

6. What are the limitations of FSM?

7. What do you mean by state equivalence and state distinguishable? Explain with example.
8. What is distinguishable state and distinguishable sequence?

9. What is k - distinguishable?

10. Define equivalent partition.

11. . Find the equivalent partition for the machines given below
A

C
D

C
G

C
12. What is incompletely specified FSM?

13. What is applicable sequence?

14. What is compatible state?

15. What is Compatible pair?

16. What is implied pair?

17. What is Merger Graph?

18. Construct Merger graph and compatibility graph

A

C
B

C
C

C
19. Construct Merger table and compatibility graph

C
B

C
C

C
20. What is Testing Table and Testing Graph?

21. Draw an algorithm to check loop free Testing Graph.

22. What is Connection Matrix?

23. Test whether a following machines is finite or not

C
B

C
C

C
D

C
E

C
F

C
24. What is Definite Machine?

25. Mention three ways of test for definiteness of a machine.

26. Find whether a following machine is definite or not

C
B

C
C

C
D

C
E

C
F

C
27. Test whether the following machine information lossless or not. If lossless find its order.

C
B

C
C

C
D

C
E

C
F

C
G

C
28. Define inverse machine and construct inverse machine for the following machines.

C
B

C
29. Explain Chomsky Classification.

30. Differentiate between symbols and alphabets of a language.

31. What do you mean by string of a language?

32. How many strings are possible over the alphabet set {a, b} of length n?

33. What is finite language?

34. What is infinite language?

35. What do you mean by ?

36. What do you mean by ?

37. How many languages are possible over ?

38. What are the valid programs in terms of Automata Theory?

39. How can we find out whether a given program is in the language or not?
40. How can we say a string is accepted by finite automata?

41. How can we say a language is accepted by finite automata?

42. Define Deterministic Finite Automata.

43. Define Non-Deterministic Automata.

44. Construct a DFA that accept all strings over the alphabets {a, b} where the string length is
divisible by two.

45. Construct a DFA that accept all strings over the alphabets {a, b} where the string length is
divisible by two.

46. Construct a DFA where | |

47. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ in the string
is two.

48. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ in the string
at most two.

49. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ in the string
is even.
50. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ in the string
is odd.

51. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ and
number of ‘b’ in the string is divisible by 3.

52. Construct a minimal DFA which accepts all strings over {0,1}, which when interpreted as binary
number is divisible by 4.
53. Construct a minimal DFA which accepts all strings over {0,1}, which when interpreted as binary
number is .

54. Construct a minimal DFA which accepts all strings over {0,1}, which when interpreted as binary
number is .

55. Construct a minimal DFA which accepts all strings over {0,1,2}, which when interpreted as
ternary number is divisible by 4.
56. Construct a minimal DFA which accepts set of all strings over {a, b} where each string starts with
an ‘a’.

57. Construct a minimal DFA which accepts set of all strings over {a, b} where each string ends with
an ‘a’.

58. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ is even and
number of ‘b’ is odd in the string.
59. Construct a DFA that accept all strings over the alphabets {a, b} where number of ‘a’ is odd and
number of ‘b’ is even in the string.

60. Construct a DFA that accept all strings over the alphabets {a, b} such that ( )
( ) .

61. Construct a minimal DFA which accepts all strings over Octal number system, which when
interpreted as binary number
62. Construct a minimal DFA which accepts set of all strings over {a, b} where each string start with
“ab”

63. Construct a minimal DFA which accepts set of all strings over {a, b} where each string contains
“ab” as a sub string.

64. Construct a minimal DFA which accepts set of all strings over {a, b} where each string starts with
‘a’ and ends with ‘b’ or vice versa.
65. Construct a minimal DFA which accepts set of all strings over {a, b} which accepts strings in
which every 'a' is followed by 'b'.

66. Construct a minimal DFA for * | +

67. Construct a minimal DFA for * | +

68. Define .

69. What do you mean by transition function of DFA? Explain.

70. What do you mean by transition function of NFA? Explain.

71. What is Dead State?

72. What is Dead Configuration?

73. Define Complementation operation of DFA.

74. Define Union operation of DFA.

75. Define Concatenation operation of DFA.

76. Define state equivalence.

77. What do you mean by non-reachable state?

78. Which one is more powerful DFA or NFA? Explain.

79. How to convert NFA to DFA.

80. Check two given DFA are equivalent or not.
81. Construct DFA from the given NFA

A NS
PS
0 1
A B A
B C B
C E D
D C C
E E E
B
C

C
D

C
82. Convert epsilon - NFA to NFA

C
B

C
83. Define Moore Machine.

84. Define Mealy Machine.

85. Construct a Moore machine that takes set of all string over {a,b} and count the number of
occurrence of substring ‘baa’.

86. Construct a Mealy machine that accepts binary number as input and produces 2’s complement
of that number as output. Assume the string is read LSB to MSB and end carry is discarded.
87. Construct a Moore machine that takes set of all string over {a, b} as input and prints ‘1’ as
output for every occurrence of ‘ab’ as a substring

88. Construct a Moore machine that takes binary numbers as in and produces residue modulo ‘3’ as
output.
 89. Convert Moore Machine to Mealy Machine.

A
B
90. Convert Mealy Machine to Moore Machine.

A
B
91. Define Regular Expression.

92. What is machine format of a regular expression?

93. What kind of language accepts regular expressions?

94. Under what operations regular sets are closed?

95. What is the difference between Null state and Null string?

96. What do you mean by primitive regular expression?

97. Find regular expression over the alphabet set {a, b} where string length is exactly two.
 98. Find regular expression over the alphabet set {a, b} where string length is exactly three.

99. Find regular expression over the alphabet set {a, b} where string length is at least two.

100. Find regular expression over the alphabet set {a, b} where string length is at most two.
101. Find regular expression over the alphabet set {a, b} where string length even.

102. Find regular expression over the alphabet set {a, b} where string length odd.

103. Find regular expression over the alphabet set {a, b} where string length is divisible by 3.
104. Find regular expression over the alphabet set {a, b} where string is .

105. Find regular expression over the alphabet set {a, b} where number of a’s are exactly two.

106. Find regular expression over the alphabet set {a, b} where number of a’s are at least two.
107. Find regular expression over the alphabet set {a, b} where number of a’s are at most two.

108. Find regular expression over the alphabet set {a, b} where number of a’s are even.

109. Find regular expression over the alphabet set {a, b} where each string starts with ‘a’.
110. Find regular expression over the alphabet set {a, b} where each string ends with ‘a’.

111. Find regular expression over the alphabet set {a, b} where each string containing an ‘a’.

112. Find regular expression over the alphabet set {a, b} where each string starting and ending with
different symbol.
113. Find regular expression over the alphabet set {a, b} where each string starting and ending with
same symbol.

114. Define Arden’s Theorem.

115. Draw a finite automata for the regular expression (a + b).

116. Draw a finite automata for the regular expression( )

117. Draw a finite automaton for the regular expression .

118. Draw a finite automata for the regular expression ( )

119. How many strings of length less than 4 contains the language described by the regular
expression ( ) ( )
120. Prove that ( ) ( )( )( ) ( )

121. Prove that ( ) ( )

122. Prove that ( )( ( )) ( )

123. Prove that ( ) (( ( ) )) ( )

124. Construct Finite Automata equivalent the Regular Expression( )( ).

125. Construct Finite Automata equivalent the Regular Expression ( )( ).

126. Construct Finite Automata equivalent the Regular Expression( ) .

127. Construct a Regular Grammar from the Regular Expression ( )( ).

128. Construct a Regular Grammar from the Regular Expression ( ) .

129. Construct a Regular Grammar from the Regular Expression *( ) *( )

Module – 2:
1. What are the different kinds of grammar in Automata Theory?

2. What is acceptor of a regular language?

3. What is generator of a regular language?

4. What is representer of a regular language?

5. How can I say a grammar is regular?

6. State two properties of Regular Grammar.

7. What is production rule?

8. Define pumping lemma for regular language.

9. Show that { | }is not regular.

10. Show that * | +is not regular.
11. Show that * | +is not regular.
12. Show that * | ( ) +is not regular.
13. Show that * | +is not regular.
Module – 3:
1. Define Derivation tree.

2. Define sentential forms.

3. What is Right most and leftmost derivation of strings.

4. Define Context Free Grammars.

5. What do you mean by Ambiguity in context free grammars?

6. What do you mean by null production in CFG? How null production will be eliminated from a
grammar?

7. Eliminate the unite production from the following grammar

8. Reduce the following grammar G into CNF. ⁄, -⁄ ⁄
9. Reduce the following grammar G into CNF. ⁄
10. Reduce the following grammar G into CNF. ⁄ ⁄ ⁄
11. Convert the following grammar G into its equivalent GNF. ⁄ ⁄
12. Convert the following grammar G into its equivalent GNF. ⁄ ⁄
13. Show that the grammar ( ) * + * + is
ambiguous.
14. Construct the grammars in CNF generating the following* | * ++
15. Write down the procedure or rule to construct the grammar G from PDA.
16. Construct the grammar G from the PDA A that accepting the language * | + by
null store.
17. Construct the grammar G from the PDA A that accepting the language * | +
by null store.
18. Construct the PDA A equivalent to the following grammar CFG: Test
whether is in
19. Construct the PDA A equivalent to the following grammar CFG: ⁄
20. Construct the PDA A equivalent to the following grammar CFG: ⁄
21. Construct the PDA A equivalent to the following grammar CFG: ⁄
22. Construct the PDA A equivalent to the following grammar CFG: ⁄ ⁄
23. Show that * | +is not CFL.
24. Show that { | }is not CFL.
25. Show that * | + is not CFL.
26. Define push down automata with block diagram of it.
27. Design the PDA for * | + that accepting by null store.
28. Design the PDA for * | * + + that accepting by final state.
29. Design the PDA A for * | * + ( ) ( )+ that accepting by final state. Test
whether is accepted by designed PDA A.
30. Design the PDA for * | + that accepting by null store.
31. Design the PDA for * | + that accepting by null store.
32. Construct a PDA to accept ( ) with equal number of ‘a’ and ‘b’ by empty stack.
33. Design the PDA for * | * + + that accepting by final state.
34. Design the PDA for * | + that accepting by final state.
35. Design the PDA for * | + that accepting by final state.
36. Design the PDA for * | + that accepting by null store.
37. Design the PDA for * | + that accepting by final state.
38. Design the PDA for * | + that accepting by final state.
39. Design the PDA for * | + that accepting by final state.
40. Design the PDA for * | + that accepting by final state.
41. Design the PDA for * | + that accepting by final state.
42. Design the PDA for * | + that accepting by final state.
Module – 4 :
1. What is Turing Machine?

2. What are different parts of the mechanical diagram of Turing Machine?

3. Where is the difference between TM and PDA?

4. What are the special features of TM?

5. Define instantaneous description of TM?

6. What are the applications of TM?

7. What is the basic difference between FA and TM?

8. What is the language accepted by TM?

9. Explain the steps required to design the TM.

10. Construct a Turing machine that accepts the language ( )
11. Construct a Turing machine that accepts the language * || | +
12. Construct a Turing machine that accepts the language ( ) .
13. Define Halting problem.