Sub Code: (CST-009) ROLL NO……………..……………..
EVEN SEMESTER EXAMINATION, 2023 – 24
2 yr B.Tech. –Computer Science&Engineering
nd
FORMAL LANGUAGES & AUTOMATA THEORY
Duration: 3:00 hrs Max Marks: 100
Note: - Attempt all questions. All Questions carry equal marks. In case of any ambiguity or missing
data, the same may be assumed and state the assumption made in the answer.
Q 1. Answer any four parts of the following. 5x4=20
a) Give DFAs that recognize the following languages:
{w Є {0,1}* | w contains 110 as a substring}
b) Convert the following Deterministic Finite Automata into Regular Expression.
c) Give context-free grammars having two variables generating the following
languages over the alphabet {a,b}
L= “The set of strings with more a’s than b’s”
d) State whether the statement is true or false and Briefly give reason in support of
your answer. “The class of context-free languages is closed under intersection”.
e) Discuss four closure properties of Regular Languages and prove that the Regular
Languages are closed under them.
f) What is Pumping Lemma for regular Language.
Q 2. Answer any four parts of the following. 5x4=20
(a) Put the following grammar into Chomsky Normal Form.
S T | TaS
T aTb | bTa | TT | Є
b) Give DFAs that recognize the following languages:
{w Є {0,1}* | w contains at least two 0’s}
c) State whether the statement is true or false and Briefly give reason in support of
your answer: “ A context free grammar G and w be a string in L(G), then the
number of leaves in a parse tree of w with respect to G can be more than the length
of w”.
d) Construct a Deterministic finite automaton to accept the set L of all strings over
{0,1} ending with 010.
e) Differentiate between Non deterministic finite automata (NFA) and deterministic
finite automata(DFA).
f) What are regular expressions? Discuss in brief operators of regular expression and
their precedence
Q 3. Answer any two parts of the following. 10x2= 20
a) Design a non-deterministic pushdown automata M that recognizes the language
L= { wwR | w Є {0,1}*}, where wR means written backwards. Give the informal
description of the PDA.
b) Design a Turing machine with no more than three states that accepts the language
L(a(a+b)*). Assume that ∑ = {a,b}. Is it possible to do thiswith a two state
machine?
c) Elaborate Chomsky and Greibach normal forms.
Q 4. Answer any two parts of the following. 10x2= 20
a) Design a Turing machine that copies strings of 1's. More precisely, find a
machine that performs the computation. Give the pseudocode of the design.
q0w |--*qfww.
b) Complete the following state transition diagram of Push Down Automata M that
recognizes
L= { aibjck | i,j,k>=0 and i=j or i=k}
c) What are Recursive languages? Discuss the Properties of recursive languages.
Q 5. Answer any two parts of the following. 10x2= 20
a) Find a grammar having single variable that generates the following language:
L = {anbn+1 | n 0}
Give the complete specification of the grammar. Construct parse tree for any two
strings w Є L and |w|=5. Show whether the grammar is ambiguous?
b) Discuss Undecidable Problems about Turing Machines.
c) Design a Turing Machine to recognize all the strings consisting of an even
number of 1’s. Give the idea of construction and transition table for the Turing
machine.
**********
