JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (November/December - 2020 - R16)
Answer any Five Questions. All Questions Carry Equal Marks.
Main
Draw the transition diagram for a NFA which accepts all the strings with either two consecutive 0’s or two consecutive 1’s.
Answer
The NFA accepts strings over the alphabet {0, 1} containing the substring 00 or 11. The machine uses a non-deterministic start state to branch into two parallel paths: one searching for 00 and one for 11.
States: q0 (start), q1, q2 (accepting for 00), q3, q4 (accepting for 11).
- q0 transitions to q0 on input 0 or 1.
- q0 transitions to q1 on input 0.
- q1 transitions to q2 on input 0.
- q2 transitions to q2 on input 0 or 1.
- q0 transitions to q3 on input 1.
- q3 transitions to q4 on input 1.
- q4 transitions to q4 on input 0 or 1.
States q2 and q4 are final states.
Define NFA with Epsilon moves.
Answer
An NFA with Epsilon moves (ε-NFA) is a 5-tuple (Q, Σ, δ, q0, F) where:
- Q is a finite set of states.
- Σ is a finite set of input symbols.
- δ is the transition function δ: Q × (Σ ∪ {ε}) → 2^Q, allowing transitions without consuming any input symbol.
- q0 is the start state.
- F is the set of final states.
The inclusion of ε-transitions allows the automaton to change its state spontaneously, which simplifies the construction of complex machines by allowing the concatenation of simpler NFAs.
Write the properties of transition function.
Answer
Sign in to view the complete answer paper.
Construct DFA accepting the set of all strings with at most one pair of consecutive 0’s and at most one pair of consecutive 1’s.
Answer
Sign in to view the complete answer paper.
Convert regular expression 01*+1 to finite automata.
Answer
Sign in to view the complete answer paper.
What are the properties of regular expressions?
Answer
Sign in to view the complete answer paper.
What are the closure properties of Regular Languages? Explain.
Answer
Sign in to view the complete answer paper.
Write about the applications of Regular expressions.
Answer
Sign in to view the complete answer paper.
Discuss about:
Context Free Grammar
Answer
Sign in to view the complete answer paper.
Left Most Derivation
Answer
Sign in to view the complete answer paper.
Right Most Derivation.
Answer
Sign in to view the complete answer paper.
What is unrestricted grammar? Give an example.
Answer
Sign in to view the complete answer paper.
Explain the language generated by unrestricted grammar.
Answer
Sign in to view the complete answer paper.
Write the procedure to convert CFG to PDA and also convert the following CFG to PDA.
A → aBB | a
B → bBB | A
C → a
Answer
Sign in to view the complete answer paper.
Define the classes P and NP problems. Also write brief note on NP-Complete and NP-Hard Problems.
Answer
Sign in to view the complete answer paper.
Explain about post correspondence problem.
Answer
Sign in to view the complete answer paper.