JNTU
JNTU B.Tech III FORMAL LANGUAGES AND AUTOMATA THEORY Previous Question Paper (January/February - 2023 - R18)
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
What is a string? Write about concatenation of two strings.
Answer
A string is a finite sequence of symbols chosen from a specified alphabet Σ. The length of a string, denoted by |w|, is the total number of symbols present in the sequence.
The concatenation of two strings x and y, denoted as xy, is the string formed by appending the symbols of string y to the end of string x. If x = a1a2...an and y = b1b2...bm, then the concatenation xy = a1a2...anb1b2...bm, with the length |xy| = |x| + |y|.
What is a Regular expression in the theory of Automata?
Answer
A Regular Expression is a formal algebraic notation used to represent and describe the set of strings accepted by a Finite Automaton, known as a Regular Language. It provides a concise way to define the patterns of strings over a given alphabet Σ.
Regular expressions are defined recursively using the following base cases and operations:
- The empty string (ε) and the empty set (∅) are regular expressions.
- Each symbol 'a' in the alphabet Σ is a regular expression.
- If r and s are regular expressions, then their union (r + s), concatenation (rs), and Kleene closure (r*) are also regular expressions.
By applying these rules, any language that can be recognized by a Deterministic Finite Automaton (DFA) or a Nondeterministic Finite Automaton (NFA) can be expressed as a regular expression.
Eliminate Useless symbols from the given grammar A→ xyz |Xyzz X → Xz |xYz Y →yYy|Xz Z → Zy | z
Answer
Sign in to view the complete answer paper.
Write the design strategy for NFA-ε.
Answer
Sign in to view the complete answer paper.
Write any two properties of Regular languages.
Answer
Sign in to view the complete answer paper.
Write about Leftmost derivation and rightmost derivation with example.
Answer
Sign in to view the complete answer paper.
Define GNF.
Answer
Sign in to view the complete answer paper.
Write the advantages of parse tree in identifying ambiguity.
Answer
Sign in to view the complete answer paper.
What do you mean by Instantaneous Description of Turing Machine?
Answer
Sign in to view the complete answer paper.
What is offline Turing Machine?
Answer
Sign in to view the complete answer paper.
Part B
Define Finite Automaton. Explain about the model of Finite Automaton.
Answer
Sign in to view the complete answer paper.
Convert the regular expression (((00)*(11)) + 01)* into an NFA.
Answer
Sign in to view the complete answer paper.
Describe in brief about applications of Finite Automata.
Answer
Sign in to view the complete answer paper.
Design a mealy machine to print out 1’s complement of an input bit string.
Answer
Sign in to view the complete answer paper.
Write the steps to construct regular expression from given DFA.
Answer
Sign in to view the complete answer paper.
Construct a NFA equivalent to the regular expression 10(0+11)0*1.
Answer
Sign in to view the complete answer paper.
Write in brief about the algebraic rules for regular expressions.
Answer
Sign in to view the complete answer paper.
Discuss in brief about applications of pumping lemma.
Answer
Sign in to view the complete answer paper.
Define Push Down Automata. Explain the basic structure of PDA with a neat graphical representation.
Answer
Sign in to view the complete answer paper.
Construct a PDA that accepts L = {0n1n | n ≥ 0}.
Answer
Sign in to view the complete answer paper.
Construct a PDA which accepts language of word over alphabet {a,b} canting {aibjck /i,j,k ∈N, i+k=j}.
Answer
Sign in to view the complete answer paper.
Define Context Free Grammar. State and explain the closure properties of CFG.
Answer
Sign in to view the complete answer paper.
Obtain Griebech Normal Form (GNF) for: S→AB, A→BS/b, B→SA/a.
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?
Answer
Sign in to view the complete answer paper.
Construct a Left most Derivation for the string 0011000 using the grammar S→A0S/0/SS, A→S1A/10?
Answer
Sign in to view the complete answer paper.
Discuss in brief about decision properties of Context free languages.
Answer
Sign in to view the complete answer paper.
Construct Turing machine for the languages containing the set of all strings of balanced paranthesis.
Answer
Sign in to view the complete answer paper.
Design Turing machine and its transition diagram to accept the language: L = {anbn | n >=1}
Answer
Sign in to view the complete answer paper.
Define LR(0) Grammar. Explain in detail about Post Correspondence Problem.
Answer
Sign in to view the complete answer paper.
What is decidability? Explain in brief about any two undecidable problems.
Answer
Sign in to view the complete answer paper.