KIET Group of Institutions: PUE Examination (2021-2022) EVEN Semester

Roll No.
___________________
KIET Group of Institutions

PUE Examination (2021-2022) EVEN Semester
Department: Department of Computer Applications

Course: MCA
Year: Ist Semester: 2nd
Subject Name: Theory of Automata and Formal Languages Subject Code: KCA- 201
Duration: 3 Hrs Max. Marks: 100
Note: Attempt all the questions of each section
Section-A (210=20)
Q. 1 Competitive BL/
Exam# CO
KC*
Differentiate between kleene closure and positive closure by giving
a 1 2/C
example.
b Let S and T be language over ={a,b} represented by the regular
expressions (a+b*)* and (a+b)*, respectively. Determine whether S GATE 2000 1 3C/P
and T are equal or not.
c Determine the regular expression for all strings over input alphabets ∑ = 3C/P
2
{0, 1} ending in either 010 or 0010.
d Determine the regular expressions represents the language: the set of all 3C/P
2
binary strings having two consecutive 0s and two consecutive 1s?
e Describe the concept of left recursion in brief. 3 2C
f Discuss when a grammar is said to be in CNF. 3 2C
g Briefly explain the decision properties of CFL. 4 2C
h Explain the additional feature PDA has when compared with NFA? 2C
4
Describe your answer by taking suitable example.
i Explain the concept of universal Turing machine with its features in 2C
5
detail.
j Explain the concept of recursive and recursive enumerable language in 2C
5
detail.
Consider the following two statements:

S1: {02n |n >= l} is a regu1ar language GATE 2012
S2: { 0m 0n 0m+n where m >= 1 and n >= 2} is a regu1ar language
Determine which of above statement(s) is/are correct with justification.
OR
Demonstrate the complement of the language accepted by the NFA
shown below? Assume ∑ = {a} and ε is the empty string.
Q. 2 1 3C/P
GATE 2013
Show that the given language is not regular L = {an bn | n ≥ 0}.

OR
Discover the regular expression for ∑ = {a,b} that generates the sets of
Q. 3 all strings with 2 3C/P
a) one a
b) all strings with at least one a
c) all strings with at least 3a’s.
 CO -Course Outcome generally refer to traits, knowledge, skill set that a student attains after completing the course successfully.
 Bloom’s Level (BL) - Bloom’s taxonomy framework is planning and designing of assessment of student’s learning.
 *Knowledge Categories (KCs): F-Factual, C-Conceptual, P-Procedural, M-Metacognitive
 #Reference to Competitive Exams (GATE, GPAT, CAT, GRE, TOFEL, NET, etc. )
Roll No. ___________________
Investigate the string "aabbabba" for leftmost derivation and rightmost
derivation using a CFG given by,
1. S → aB | bA
2. S → a | aS | bAA
Q. 4 3. S → b | aS | aBB 3 3C/P
And also construct a derivation tree.
OR
Express the CFG in terms formal definition. Also discover the CFG that
contains any number of a or b over {a, b}.
Briefly explain the closure properties of CFL.
Q. 5 OR 4 2C/P
Describe the formal definition of PDA and compare DPDA and NPDA.
Explain the concept of Post correspondence problem and obtain the
solution for the following correspondence system. A= {ba, ab, a, baa, b}
B= { bab, baa, ba, a, aba}. The input set is {a, b}.
OR
Investigate the given statements and explore for answers. GATE 2012
Q. 6 5 4C/P
1) Does a given program ever produce an output?
2) If L is a context-free language, then is L’ (complement of L) also
context-free?
3) If L is a regular language, then is L’ also regular?
4) If L is a recursive language, then, is L’ also recursive?
Section-C (105=50)
Illustrate the steps of DFA minimization and also minimize the DFA
shown below.
Q. 7 OR 1 3C/P
Explore the formal definition of Moore and Mealy machine and convert
the given Moore machine into its equivalent Mealy machine.
Q. 8 Draw a DFA from the given regular expression 10 + (0 + 11) 0*. 2 3C/P
OR
State Arden’s theorem and express the regular expression for the
Roll No. ___________________
following DFA using Arden’s Theorem
Explore the steps to Convert a CFG into Greibach Normal Form. Modify
the given CFG to GNF with productions
S → XB | AA
A → a | SA
B → b
X → a
OR
Q. 9 3 3C/P
Explore the steps to Convert a CFG into Chomsky Normal Form.
Modify the given CFG to CNF with productions
S->a|aA|B|C
A->aB | ε
B-> Aa
C-> cCD
D->DD
Q. 10 Explore the formal definition of push down automata. Transform the
given language L = {an c bn for n≥1} into PDA
OR 4 4 C/P
Transform the given language L= {an bn cn for n≥1} into PDA using two
stack and also write its transition function corresponding to every state.
Q. 11 Transform the language L= {a n bn cn for n≥1} into Turing machine for
accepting.
OR
Explore the following using a short note on 5 4 C/P
a) Halting problem
b) Church-Turing Thesis
c) Compare FA, PDA and TM with each other.

KIET Group of Institutions: PUE Examination (2021-2022) EVEN Semester

Uploaded by

Copyright:

Available Formats

KIET Group of Institutions: PUE Examination (2021-2022) EVEN Semester

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

KIET Group of Institutions: PUE Examination (2021-2022) EVEN Semester

Uploaded by

Copyright:

Available Formats

Roll No.

KIET Group of Institutions

Department: Department of Computer Applications

Consider the following two statements:

Show that the given language is not regular L = {an bn | n ≥ 0}.

You might also like