JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (December - 2018 - R13)
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 DFA.
Answer
A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q₀, F) where Q is a finite set of states, Σ is a finite set of input symbols, δ: Q × Σ → Q is the transition function, q₀ ∈ Q is the start state, and F ⊆ Q is the set of final states. It is deterministic because for every state and input symbol, there is exactly one transition to a next state.
Design FA which accepts set of all strings ending with 00.
Answer
The FA consists of three states: q₀ (start, no 0s seen), q₁ (seen one 0), and q₂ (final, seen 00). Transitions: δ(q₀, 0) = q₁, δ(q₀, 1) = q₀, δ(q₁, 0) = q₂, δ(q₁, 1) = q₀, δ(q₂, 0) = q₂, δ(q₂, 1) = q₀.
Define Left linear Grammar.
Answer
Sign in to view the complete answer paper.
Give the regular expression for the language all string over alphabet {0,1} containing at least two 0’s.
Answer
Sign in to view the complete answer paper.
What is ambiguity in CFG?
Answer
Sign in to view the complete answer paper.
Write the context free grammar for the language L={anb2n/n≥1}
Answer
Sign in to view the complete answer paper.
Give Instantaneous description ID of Turing Machine.
Answer
Sign in to view the complete answer paper.
Define Type 0 Grammar.
Answer
Sign in to view the complete answer paper.
List any 2 NP Hard Problems.
Answer
Sign in to view the complete answer paper.
Define Turing reducibility.
Answer
Sign in to view the complete answer paper.
Part B
Convert the following NFA with € - moves to DFA shown in figure 1.
Answer
Sign in to view the complete answer paper.
Minimize the following DFA shown in figure 2.
Answer
Sign in to view the complete answer paper.
Check whether the following two Finite Automaton’s are equivalent or not?
Answer
Sign in to view the complete answer paper.
Convert the following NFA with € moves to DFA in figure 5.
Answer
Sign in to view the complete answer paper.
Construct an NFA for the following Regular expression:
a) 01[((10)*+111)*+0]*1
b) ((01+10)*00)*
Answer
Sign in to view the complete answer paper.
Find the regular grammar for the following Finite Automate shown in figure 6.
Answer
Sign in to view the complete answer paper.
Construct FA for the following regular expressions (0+1)*(1+00)(0+1)*.
Answer
Sign in to view the complete answer paper.
Convert the following grammar to Chomsky Normal Form S→ ABA, A→ aA | Є, B→ bB | Є and simplify the grammar.
Answer
Sign in to view the complete answer paper.
Write and explain closure properties of Context Free Languages.
Answer
Sign in to view the complete answer paper.
State the Pumping Lemma for Context Free Languages.
Answer
Sign in to view the complete answer paper.
Design Push down Automata for the language L = {anb2n | n≥1}.
Answer
Sign in to view the complete answer paper.
Design Turing Machine for the Language L={ anbncn /n≥1 }
Answer
Sign in to view the complete answer paper.
List the Closure properties of recursive Languages.
Answer
Sign in to view the complete answer paper.
Design Turing Machine to compute the function n!
Answer
Sign in to view the complete answer paper.
Design TM for performing proper subtraction of two numbers.
Answer
Sign in to view the complete answer paper.
Briefly write about Universal Turning Machine (UTM).
Answer
Sign in to view the complete answer paper.
What do you mean by NP Complete? List any 6 NP Complete Problems.
Answer
Sign in to view the complete answer paper.
Discuss about turing Reducibility.
Answer
Sign in to view the complete answer paper.
Write about: i) Post Correspondence Problem ii) Halting problem of TM.
Answer
Sign in to view the complete answer paper.