JNTU
JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (April - 2018 - 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. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Define DFA.
Answer
A Deterministic Finite Automaton (DFA) is a 5-tuple (Q, Σ, δ, q0, F) where Q is a finite set of states, Σ is a finite set of input symbols, δ: Q × Σ → Q is the transition function, q0 ∈ Q is the start state, and F ⊆ Q is the set of final states. For every state and input symbol, there is exactly one transition to a next state.
Write about the applications of Finite Automata?
Answer
Finite Automata are used in several key areas:
- Lexical analysis in compilers for token recognition.
- Pattern matching and searching in text editors and grep tools.
- Design and verification of digital circuits and communication protocols.
- Natural language processing for morphological analysis.
If a Regular grammar G is given by S→aS/a Find DFA (M) accepting L(G)?
Answer
Sign in to view the complete answer paper.
Construct a regular grammar for L= {0n11/n>=1}.
Answer
Sign in to view the complete answer paper.
For the Grammar {S→AS/a, A→SbA/SS/ba} construct Left most derivation for the string aabbaaa?
Answer
Sign in to view the complete answer paper.
Define Push Down Automata.
Answer
Sign in to view the complete answer paper.
What is the purpose of studying Turing Machine?
Answer
Sign in to view the complete answer paper.
Write a Context free grammar for the language {0n1n/n>=1}.
Answer
Sign in to view the complete answer paper.
Give an example of un decidable problem.
Answer
Sign in to view the complete answer paper.
Define Post correspondence Problem.
Answer
Sign in to view the complete answer paper.
Part B
Construct Minimum state Automata for the given DFA.
| δ | 0 | 1 |
|---|---|---|
| →Q1 | q2 | q6 |
| q2 | q1 | q3 |
| *q3 | q2 | q4 |
| q4 | q4 | q2 |
| q5 | q4 | q5 |
| *q6 | q5 | q4 |
Differentiate between NFA and DFA.
Answer
Sign in to view the complete answer paper.
Design DFA for the following over {a,b}. i) All strings containing not more than three a’s. ii) All strings that has at least two occurrences of b between any two occurrences of a.
Construct a DFA accepting the set of all strings ending with 00?
Answer
Sign in to view the complete answer paper.
Define Regular Expression? Explain about the Properties of Regular Expressions.
Construct a DFA for the Regular Language consisting of any number of a’s and b’s.
Answer
Sign in to view the complete answer paper.
Construct a DFA for the Regular expression (0+1)* (00+11) (0+1)*.
Explain about the identity rules of Regular Expressions.
Answer
Sign in to view the complete answer paper.
Define Ambiguous Grammar. Check whether the grammar S→aAB, A→bC/cd, C→cd, B→c/d Is Ambiguous or not?
Construct a PDA for the following grammar S→AA/a, A→SA/b.
Answer
Sign in to view the complete answer paper.
Show that for every PDA there exists a CFG such that L(G)=N(P).
Convert the grammar S→0AA, A →0S/1S/0 to a PDA that Accepts the same Language by Empty Stack.
Answer
Sign in to view the complete answer paper.
Construct a Turing Machine that will accept the Language consists of all palindromes of 0’s and 1’s?
Explain about types of Turing Machine.
Answer
Sign in to view the complete answer paper.
Obtain GNF for S→AB, A→BS/b , B→SA/a.
Design a Turing Machine for L={0n1m0n1m/m,n>=1}.
Answer
Sign in to view the complete answer paper.
Discuss in brief about NP Hard problems.
Explain about the Decidability and Undecidability Problems.
Answer
Sign in to view the complete answer paper.
Give an overview of recursively enumerable language.
Give the correspondence between P, NP and NP-complete problems.
Answer
Sign in to view the complete answer paper.