JNTU
JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (May - 2019 - R16)
Note: This question paper contains two parts A and B. Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit.
PART - A
Define Kleene Closure and Positive Closure?
Answer
Kleene Closure of a set of strings Σ, denoted by Σ*, is the set of all strings of length zero or more formed by concatenating zero or more symbols from Σ. Positive Closure, denoted by Σ+, is the set of all strings of length one or more formed by concatenating one or more symbols from Σ. Mathematically, Σ+ = Σ* - {ε}.
Define Moore Machine?
Answer
A Moore Machine is a finite state machine whose output values are determined solely by its current state. It is defined by a 6-tuple (Q, Σ, Δ, δ, λ, q₀), where Q is a finite set of states, Σ is the input alphabet, Δ is the output alphabet, δ is the transition function (Q × Σ → Q), λ is the output function (Q → Δ), and q₀ is the initial state.
Define a Regular Expression.
Answer
Sign in to view the complete answer paper.
Find the simplified regular expression for the following regular expression r(r*r + r*) + r*?
Answer
Sign in to view the complete answer paper.
Define Context Free Grammar.
Answer
Sign in to view the complete answer paper.
Define Push Down Automata.
Answer
Sign in to view the complete answer paper.
Define Turing machine.
Answer
Sign in to view the complete answer paper.
What is Chomsky Normal Form?
Answer
Sign in to view the complete answer paper.
What is undecidable problem?
Answer
Sign in to view the complete answer paper.
Compare recursive and recursive enumerable languages.
Answer
Sign in to view the complete answer paper.
PART - B
Construct NFA with ε which accepts a language consisting the strings of any number of 0’s followed by any number of 1’s followed by any number of 2’s And also convert into NFA without ε transitions.
Answer
Sign in to view the complete answer paper.
Construct the Moore machine to determine residue mod 3 and convert into Mealy machine.
Answer
Sign in to view the complete answer paper.
Test whether the following two FSM’s are equivalent.
Answer
Sign in to view the complete answer paper.
Apply pumping lemma for the language L={an | n is prime} and prove that it is not regular?
Answer
Sign in to view the complete answer paper.
Construct the regular expression corresponding to the language accepted by following DFA.
Answer
Sign in to view the complete answer paper.
Elaborate on left most derivation and right most derivation.
Answer
Sign in to view the complete answer paper.
Design Push down Automata for L = {a2nbn | n ≥ 1}.
Answer
Sign in to view the complete answer paper.
Construct the CFG for the PDA M = ({q0,q1}, {0,1}, {R,Z0}, δ, q0, Z0, Φ) and δ is given by
δ(q0,1,Z0)=(q0,RZ0)
δ(q0,1,R)=(q0,RR)
δ(q0,0,R)=(q1,R)
δ(q1,0, Z0)=(q0, Z0)
δ(q0,ε, Z0)=(q0,ε)
δ(q1,1,R)=(q1,ε).
Answer
Sign in to view the complete answer paper.
List out and discuss the closure properties of CFL.
Answer
Sign in to view the complete answer paper.
Construct CFG without ε – production from the one which is given below:
S → a | Ab | aBa
A → b | ε
B → b | A
Answer
Sign in to view the complete answer paper.
Design a Turing Machine to accept L={WcWR | W is in (a+b)*}.
Answer
Sign in to view the complete answer paper.
Discuss in brief about NP Hard problems.
Answer
Sign in to view the complete answer paper.
Discuss the examples of undecidable problems.
Answer
Sign in to view the complete answer paper.
Explain about the undecidable problems about turing machines.
Answer
Sign in to view the complete answer paper.
Distinguish between class P and class NP Problems.
Answer
Sign in to view the complete answer paper.