JNTU
JNTU B.Tech II FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (February - 2024 - R16)
Note: i) Question paper consists of Part A, Part B. ii) Part A is compulsory, which carries 25 marks. In Part A, answer all questions. iii) In Part B, Answer any one question from each unit. Each question carries 10 marks and may have a, b as sub questions.
Part A
Identify the elements of finite automata.
Answer
A finite automaton is formally defined by a 5-tuple (Q, Σ, δ, q₀, F), where the elements are:
- Q: A finite set of states.
- Σ: A finite set of input symbols called the alphabet.
- δ: The transition function, defined as δ: Q × Σ → Q, which maps a state and an input symbol to the next state.
- q₀: The initial or start state, where q₀ ∈ Q.
- F: The set of final or accepting states, where F ⊆ Q.
Design FA with Σ = {0, 1} accepts even number of 0's and even number of 1's.
Answer
To accept a string with an even number of 0's and an even number of 1's, the finite automaton requires four states to track the parity of both symbols. Let the states be defined as follows:
- q0: Even number of 0's, Even number of 1's (Start and Final State)
- q1: Even number of 0's, Odd number of 1's
- q2: Odd number of 0's, Even number of 1's
- q3: Odd number of 0's, Odd number of 1's
The transitions are defined as:
The automaton starts at q0, which is also the only accepting state, as it represents the condition where both counts are zero (an even number).
Outline the operations of Regular Language.
Answer
Sign in to view the complete answer paper.
How is the Pumping Lemma used to prove that a language is not regular?
Answer
Sign in to view the complete answer paper.
Identify the properties of parse tree.
Answer
Sign in to view the complete answer paper.
Construct a CFG for the regular expression (0+1)*.
Answer
Sign in to view the complete answer paper.
Discover the features of the Turing machine.
Answer
Sign in to view the complete answer paper.
State one challenge involved in converting PDA to an equivalent CFG.
Answer
Sign in to view the complete answer paper.
Identify one example of an undecidable problem concerning Turing Machines.
Answer
Sign in to view the complete answer paper.
What is recursively enumerable language?
Answer
Sign in to view the complete answer paper.
Part B
Compare the characteristics of NFAs with DFAs.
Answer
Sign in to view the complete answer paper.
Design a DFA L(M) = {w | w ε {0, 1}*} and W is a string that does not contain consecutive 1's.
Answer
Sign in to view the complete answer paper.
Compare transition diagrams and transition tables in detail.
Answer
Sign in to view the complete answer paper.
Describe the steps involved in the algorithm for eliminating ε-transitions from a finite automaton.
Answer
Sign in to view the complete answer paper.
Write the regular expression for the language L over Σ = {0, 1} such that all the string do not contain the substring 01.
Answer
Sign in to view the complete answer paper.
Prove that every language defined by a regular expression is also defined by a finite automata.
Answer
Sign in to view the complete answer paper.
Construct the FA for regular expression 0*1 + 10.
Answer
Sign in to view the complete answer paper.
Discuss real-world applications of Regular Expressions.
Answer
Sign in to view the complete answer paper.
Illustrate about derivations in the context of CFGs.
Answer
Sign in to view the complete answer paper.
Let, L (G) = {a^m b^n | m > 0 and n ≥ 0}. Find out the grammar G which produces L(G).
Answer
Sign in to view the complete answer paper.
Discuss Deterministic Pushdown Automata.
Answer
Sign in to view the complete answer paper.
Derive the string "aabbabba" for leftmost derivation and rightmost derivation using a CFG.
Answer
Sign in to view the complete answer paper.
Explain the concept of Chomsky Normal Form for Context-Free Grammars with example.
Answer
Sign in to view the complete answer paper.
Construct TM for the addition function for the unary number system.
Answer
Sign in to view the complete answer paper.
Analyze the running time complexity of converting a context-free grammar to Chomsky Normal Form.
Answer
Sign in to view the complete answer paper.
Interpret Turing Machine program with example.
Answer
Sign in to view the complete answer paper.
Explain NP-complete of SAT problem.
Answer
Sign in to view the complete answer paper.
Explain Rice’s theorem and properties of RE Language.
Answer
Sign in to view the complete answer paper.
State the properties of recursively enumerable sets which are undecidable.
Answer
Sign in to view the complete answer paper.
Obtain the solution for the following system of posts correspondence problem: A = {100, 0, 1}, B = {1, 100, 00}
Answer
Sign in to view the complete answer paper.