School of Computer Science and Engineering

Department of Computer Science & Application

Name of the Course: Formal Language Automata Theory (17YCS501)

Unit No.1
Question Bank

Asked in
[Link]. Unit Question Marks CO BL
Competitive
Exam
1. I Define the concept of a finite state machine (FSM) 2 CO1 L2 MPSC 2022

2. I Illustrate how a transition diagram helps in recognizing languages. 2 CO1 L1 GATE 2021

3. I Define language acceptance by a finite automaton 2 CO1 L2 GATE 2021

4. I Define deterministic finite automaton (DFA) 2 CO1 L2 MPSC 2015

5. I Define non-deterministic finite automaton (NFA). 2 CO1 L2 GATE 2021

6. I Describe the role of an alphabet in formal languages. 2 CO1 L1 MPSC 2007

7. I Define the significance of the acceptance of strings in automata theory? 2 CO1 L2 MPSC 2007

8. I Define Moore Machine 2 CO1 L2 --

9. I Define Mealy Machine. 2 CO1 L2 MPSC 2009

Page 1 of 15
 I Define: 1)Strings 2)Alphabet 2 CO1 L2 --

11. I Define regular expressions and list some common identity rules. 2 CO1 L1

12. II Define pumping lemma for regular sets. 2 CO2 L2

13. III Illustrate the closure properties of regular sets. 2 CO3 L2

14. III Discuss the significance of right linear and left linear grammars 2 CO3 L2

15. III How does the pumping lemma prove non-regularity of languages? 2 CO3 L1

16. III Differentiate between right-most and left-most derivations. 2 CO3 L2 MPSC 2022

17. III Define derivation trees used in parsing 2 CO3 L2 GATE 2021

18. III Define regular sets and regular expressions related 2 CO3 L2

19. III Define process of converting a regular grammar into a finite automaton. 2 CO3 L1 MPSC 2015

20. III Define significance of context-free grammars in syntax analysis 2 CO3 L2

21. III Define ambiguity in context-free grammars with an example 2 CO3 L1 MPSC 2022

22. II Define Chomsky Normal Form (CNF) 2 CO2 L1

23. II Define Greibach Normal Form (GNF) 2 CO2 L2 GATE 2021

24. I Define concept of pushdown automata 2 CO1 L1 MPSC 2015

25. I Define pumping lemma for context-free languages 2 CO1 L1

26. IV Define role of a stack in a pushdown automaton 2 CO4 L2

27. IV Define context-free languages used in parsing programming languages 2 CO4 L2

Page 2 of 15
28. IV Enlist the application of pumping lemma 2 CO4 L1

29. IV Define CFG and PDA inter-convertible? 2 CO4 L2

30. IV Define concatenation? 2 CO4 L2

31. IV Define a Turing machine and its components. 2 CO4 L2

32. IV illustarte is the role of a tape in a Turing machine? 2 CO4 L1

33. IV Define the significance of recursively enumerable languages in automata theory 2 CO4 L2

34. IV Define the relationship between context-sensitive languages and linear bounded automata. 2 CO4 L2 MPSC 2022

35. IV Define computable functions in the context of Turing machines 2 CO4 L2 GATE 2021

36. IV Define the significance of the halting problem in Turing machines 2 CO4 L1 GATE 2021

37. V Define how Turing machines used to simulate algorithms? 2 CO5 L2

38. V Describe how a Turing machine can be used to model real-world computations 2 CO5 L2

39. V Define concept of decidability in the context of Turing machines 2 CO5 L2

40. V State the role of Turing machines in the theory of computation. 2 CO5 L1

41. V Define the role of a compiler in software development? 2 CO5 L2

42. V Define the significance of lexical analysis in the compilation process. 2 CO5 L2

43. V Discuss the various phases involved in the compilation process 2 CO5 L2

44. V Define the front-end and back-end of a compiler. 2 CO5 L1

CO5
Page 3 of 15
 45. V Define the concept of top-down parsing in syntax analysis. 2 L2

46. V Define importance of parse trees in syntactic analysis? 2 CO5 L2

47. V Define differences between LL and LR parsing techniques 2 CO5 L2

48. V Discuss the importance of error detection and recovery in syntax analysis. 2 CO5 L1

49. IV Define how LR(1) parsing works in syntax analysis 2 CO4 L2

50. IV Define lexical analysis generate tokens from a source code? 2 CO4 L2

Asked in
[Link]. Unit Question Marks CO BL
Competitive
Exam
1. I Differentiate between DFA and NFA 8 CO1 L1

2. I Distinguish between :Mealy machine and Moore machine 8 CO1 L1

3. I Draw the DFA for the language accepting strings ending with 00 over input alphabet ∑ 8 CO1 L2
={0,1}
4. I Construct DFA for checking whether a string over alphabet {a,b} contains a substring abb 8 CO1 L1

5. I Draw the DFA for the language accepting strings ending with 11 over input alphabet ∑ 8
CO1 L1 GATE 2021
={0,1}

6. I Explain epsilon closure with suitable example 8 CO1 L2 MPSC 2007

7. I Define the finite automaton model and describe its role as a language recognizer. 8 CO1 L3 MPSC 2007

Describe how transition diagrams are used to represent finite automata. 8 CO1 L3 --
Page 4 of 15
 I
9. I Discuss the working of Moore and Mealy machines, highlighting the differences in their state 8
CO1 L4 MPSC 2009
transitions and outputs.

10. I Design a DFA that reads strings made up of letters in the word CHARIOT and recognizes 8 --
CO1 L4
these strings that contain the word CAT as a substring.

11. I Design a DFA that reads strings made up of letters in the word CHARIOT and recognizes 8
CO1 L1
these strings that contain the word RAT as a substring

12. I Design a DFA which can accept a decimal number divisible by 3 8 CO1 L1

13. I Design a DFA which can accept a decimal number divisible by 4 8 CO1 L2

14. I Covert to a DFA the following NFA 8

0 1
p {p,q} {p}
CO1 L1
q {r} {r}
r {s} O
s *
{s} {s}

15. I Design a Moore machine for the 1’s Complement of binary number 8 CO1 L1

16. I Covert to a DFA the following NFA 8 CO1 L2 MPSC 2015

0 1
Page 5 of 15
 p {q,s} {q}
q {r} {q,r}
r {s} {p}
s *
O {p}

17. I Design DFA for a language of string 0 and 1 that ending with 1 8 CO1 L3

18. I Explain closure property of language accepted by a DFA 8 CO1 L3 MPSC 2016

19. I Explain limitations of finite automata 8 CO1 L4

20. I Construct DFA for checking whether a string over alphabet {a,b} contains a substring abba 8 CO1 L4

21. I Construct Finite automata recognising for regular expressions 1 (01+10)* + 0 8

CO1 L1
(11+10)*

22. I Construct Finite automata recognising for regular expressions 1 (1+10)* + 10 (0+01)* 8 CO1 L1 GATE 2021

23. II Construct Finite automata recognising for regular expressions 01[((10*)+111*)+0]*1 8 CO2 L2 GATE 2021

24. II Construct Finite automata recognising for regular expressions (0+1) * (010+101) 8
CO2 L1
(0+1)*

25. II Construct Finite automata recognising for regular expressions 10 + (0+11) 0* 1 8 CO2 L1 MPSC 2018

26. II Construct DFA recognising for regular expressions (11+00)* 8 CO2 L2

27. II Construct DFA recognising for regular expressions (111+100)*0 8 CO2 L3

28. II Explain pumping lemma and give its application in details 8 CO2 L3

Page 6 of 15
 II Using Pumping lemma for regular sets prove that the language L={0m 1n 0m+n | m>=1 and MPSC 2019
8 CO2 L4
n>=1} is not regular

30. II Using Pumping lemma for regular sets prove that the language L={anbanb | n>=1} is not
8 CO2 L4
regular

31. II Explain closure properties of regular langauge 8 CO2 L1

32. II Explain Sentential form of grammer 8 CO2 L1 GATE 2021

33. II Explain left linear and right linear grammar with suitable example 8 CO2 L2 GATE 2021

34. II Explain concept of CNF & GNF with suitable example 8 CO2 L1

35. II Let G be the Grammer 8

S→ aB | bA
A→ bAA | aS | a CO2 L1
B → aBB | bS | b
For string aaabbabbba Find Left most Derivation, Right most derivation and Parse Tree

36. II Construct NFA for the regular expression ba+ba* 8 CO2 L2

37. II Convert following right linear grammar to its equivalent left linear grammar MPSC 2018
S→ 1B | 0A
A→ 0C | 1A | 0 8 CO2 L3
B → 1B | 1A | 1
C → 0 | 0A

38. II Explain regular grammar with left linear & right linear grammar. 8 CO2 L3

Page 7 of 15
 II Let G be the Grammer 8
S→ aB | bA
A→ bAA | aS | a CO2 L4
B → aBB | bS | b
For string aabbabba Find Left most Derivation, Right most derivation and Parse Tree

40. II Let G be the Grammer 8

S→ T00T
CO2 L4 GATE 2022
T→ 0T | 1T | €
For string 1000111 Find Left most Derivation, Right most derivation and Parse Tree

41. III Explain ambiguity in grammar with suitable example 8 CO3 L1 GATE 2021

42. III Explain Arden’s Theorem with suitable example 8 CO3 L1

43. III Convert the following grammar to CNF.

S→ bA|aB
8 CO3 L2
A→ bAA|aS|a
B → aBB|bS|b

44. III Convert the grammar given below to its equivalent CNF
S → PQP
8 CO3 L1
P → 0P | €
Q → 1Q | €

45. III Convert the following grammar to CNF. 8 CO3 L1

S→ Aba
Page 8 of 15
 S→ abb
B → Ac

46. III Convert the following grammar to GNF. 8

S→ ABA | AB | BA |AA | A | B
CO3 L2 GATE 2021
A→ aA|a
B → bB|b

47. III State and Explain closure properties of CFLs 8 CO3 L3 GATE 2021

48. III Write short note: Application of CFG for parsing 8 CO3 L3

49. III Convert the following grammar to CNF. 8

S→ aB
S→ bA
A→a
A → aS CO3 L4
A → bAA
B→b
B → bS
B → aBB

50. III Construct PDA for accepting a language

8 CO3 L4
{L= an bn | n>=1}.

51. III Construct PDA for accepting a language 8 CO3 L1

Page 9 of 15
 {L= an b2n | n>=1}.
52. III Construct PDA for accepting a language 8
CO3 L1 GATE 2021
{L= 0n 1n | n>=1}.
53. III Construct PDA for accepting a language 8
CO3 L2 GATE 2021
{L= 0n 12n | n>=1}.
54. III Design a PDA for detection of palindrome over {a,b} 8 CO3 L1

55. III Explain the model of a Push Down Automata (PDA) and its role in accepting context-free 8
CO3 L1
languages.
56. III Differentiate between acceptance by final state and acceptance by empty stack in PDA. 8 CO3 L2

57. III What is the significance of the pumping lemma for context-free languages in relation to PDA? 8 CO3 L3

58. III Explain the acceptance mechanism of PDA using an example language. 8 CO3 L3 GATE 2022

59. III Illustrate how a PDA can be used to recognize a language of balanced parentheses 8 CO3 L4 GATE 2021

60. III Explain the role of the stack in PDA and how it is used during language recognition. 8 CO3 L4

61. IV Explain a Turing Machine (TM) and describe its components. 8 CO4 L1

62. IV Explain the concept of computable functions and recursively enumerable languages with 8
CO4 L1
respect to Turing Machines.
63. IV Describe Church's hypothesis? Discuss its significance in computability theory. 8 CO4 L2

64. IV Differentiate between different types of Turing Machines 8 CO4 L1

65. IV Explain the concept of Linear Bounded Automata (LBA) and how it relates to context- 8 CO4 L1 GATE 2021

Page 10 of 15
 sensitive languages
66. IV Differentiate between a Turing Machine and a Finite Automaton. 8 CO4 L2 GATE 2021

67. IV What are recursively enumerable languages? How are they related to Turing Machines? 8 CO4 L3

68. IV Describe the role of a Turing Machine in recognizing recursively enumerable languages. 8 CO4 L3

69. IV Design a simple Turing Machine to recognize the language 8

CO4 L4 GATE 2023
{L= an bn | n>=1}.
70. IV Explain the concept of a Universal Turing Machine. How does it differ from a standard Turing 8
CO4 L4
Machine?
71. IV Discuss the limitations of Turing Machines. Can a Turing Machine solve every problem? 8 CO4 L1

72. IV What are the different types of Turing Machines? Describe at least two with examples. 8 CO4 L1

73. IV Explain Application of Turing Machine? 8 CO4 L2

74. IV Construct a Turing Machine for R = aba*b 8 CO4 L1

75. IV Construct Turing Machine that accepts strings with equal number 0 and 1 8 CO4 L1 GATE 2021

76. IV Differentiate between P and NP classes 8 CO4 L2

77. IV Explain representation of Turing Machine 8 CO4 L3

78. IV Explain Extension of Turing Machine 8 CO4 L3

79. IV Explain formal definition of Turing Machine 8 CO4 L4

80. IV Design TM that replaces every occurrence of abb by baa 8 CO4 L4

Page 11 of 15
 V Explain compiler and explain its role in the software development process. 8 CO5 L1

82. V Describe the phases of a compiler, including lexical analysis, syntax analysis, and semantic 8
CO5 L1
analysis.
83. V Differentiate between compiler front-end and back-end? Explain with examples. 8 CO5 L2 GATE 2023

84. V Differentiate between top-down and bottom-up parsing techniques in syntax analysis. 8 CO5 L1

85. V Explain the working of LL(1) and LR(1) parsing techniques with an example. 8 CO5 L1

86. V What are the different phases of a compiler? Briefly explain each phase. 8 CO5 L2

87. V Describe the role of code generation in the compilation process. What challenges can arise 8
CO5 L3
during this phase?
88. V What is a parse tree? Explain its role in the syntax analysis phase of a compiler. 8 CO5 L3 GATE 2024

89. V Generate a parse tree for the string a + b * c using a given context-free grammar (CFG). 8 CO5 L4

90. V Explain how a parse tree is constructed using a top-down parsing technique. 8 CO5 L4

91. V What are the differences between a parse tree and a syntax tree? Provide examples to 8
CO5 L1
illustrate your answer.
92. V Generate a parse tree for the arithmetic expression (3 + 5) * 2 based on a given
8 CO5 L1
grammar for arithmetic expressions.
93. V Describe how parse trees help in detecting syntax errors during compilation. 8 CO5 L2

94. V Explain the concept of a derivation tree and its relationship with the parse tree. 8 CO5 L1

95. V How are parse trees used in semantic analysis and code generation in the compiler process? 8 CO5 L1 GATE 2021

Page 12 of 15
96. V How does ambiguity in a grammar affect parse tree generation? Explain with an example. 8 CO5 L2 GATE 2020

97. V Explain Halting problem in Turing machine 8 CO5 L3

98. V Explain un decidability of post correspondence problem 8 CO5 L3 GATE 2023

99. V Explain P and NP class Problem 8 CO5 L4

100. V Explain satisfiability problem (SAT) 8 CO5 L4

101. V Explain Tractable and Intractable Problem 8 CO5 L1 GATE 2021

102. V Explain the model of linear bounded Automata 8 CO5 L1 GATE 2024

103. V Explain Deterministic Turing Machine 8 CO5 L2

104. V Explain Non Deterministic Turing Machine 8 CO5 L1

105. V Explain Bottom up parsing 8 CO5 L1

106. V Explain shift reduce parsing 8 CO5 L2 GATE 2021

107. V Explain Halting problem 8 CO5 L3 GATE 2023

108. V Prove that the class of regular languages is closed under: 8

1. Union CO5 L3
2. Concatenation

Kleene star
109. V Define the class P and class NP. What is the significance of the P vs NP problem? 8 CO5 L4

110. V Explain NP-complete problems? Give an example and explain why it is NP-complete. 8 CO5 L4 GATE 2022
Page 13 of 15
 111. V Define NP-completeness. State Cook’s theorem and explain its significance. 8 CO5 L1 GATE 2024

112. V Prove that SAT (the boolean satisfiability problem) is NP-complete. 8 CO5 L1

113. V Define Church-Turing Thesis? Why is it important for the study of computation? 8 CO5 L2

114. V Explain Multi-tape Turing Machine 8 CO5 L1

115. V Describe two different ways to define PDA 8 CO5 L1 GATE 2021

116. V Describe Tractable and Intractable Problem 8 CO5 L2

117. V Explain the model of linear bounded Automata 8 CO5 L3

118. V Describe Deterministic Turing Machine 8 CO5 L3

119. V Explain Non Deterministic Turing Machine 8 CO5 L4

120. V Describe the role of code generation in the compilation process. What challenges can arise 8 CO5 L4
during this phase?

Name and signature of Course Co Ordinator

Page 14 of 15