JNTU
JNTU B.Tech III AUTOMATA AND COMPILER DESIGN Previous Question Paper (October - 2020 - R15)
Answer any five questions. All questions carry equal marks.
Main
Write the process of converting an NFA into DFA. Convert the following NFA in to DFA. Check the acceptability of the string 11010 on both the FAs.
Answer
The conversion of an NFA to a DFA is performed using the Subset Construction Algorithm (or powerset construction). The process involves creating a DFA where each state represents a set of NFA states. The steps are: 1. Start with the epsilon-closure of the NFA start state as the DFA start state. 2. For each DFA state and each input symbol, find the set of all NFA states reachable from the current set of states. 3. Treat this new set as a new DFA state. 4. Repeat until no new states are created. A DFA state is accepting if it contains at least one accepting state of the NFA.
Given the NFA (assuming standard transitions for the string 11010, e.g., q0 on 1 goes to {q0, q1}, q1 on 1 goes to {q2}, q2 on 0 goes to {q3}, q3 on 1 goes to {q3}, q3 on 0 goes to {q3}): The resulting DFA states are subsets of {q0, q1, q2, q3}. For the string 11010, the NFA follows paths leading to the final state if the path exists within the set of transitions. The DFA mimics this by tracking the set of possible states simultaneously; if the final DFA state reached after processing '11010' contains the NFA's final state, the string is accepted by both.
Write down the applications of finite automata.
Answer
Finite automata are widely used in computing for pattern matching and system modeling. Key applications include:
- Lexical Analysis: Compilers use finite automata to recognize tokens (keywords, identifiers, operators) in source code by defining regular expressions.
- Text Searching: Algorithms like KMP or Aho-Corasick utilize finite automata to efficiently search for patterns within large bodies of text.
- Protocol Verification: Modeling communication protocols as state machines to ensure they are free from deadlocks and logical errors.
- Hardware Design: Designing sequential circuits and control units in digital systems where the next state depends on the current state and input.
- Natural Language Processing: Used in morphological analysis and spell checkers to validate word structures based on predefined rules.
Define a regular expression. Give Regular expressions for the following languages:
- String over the alphabet {a, b} ending with ab
- Strings over the alphabet {0, 1} that contain substring 10.
- Strings over the alphabet {0, 1} that contain 1 in the 3rd position from right end.
Answer
Sign in to view the complete answer paper.
Define a Context Free Grammar. Find CFG generating the following languages:
- Language of arithmetic expressions over integer values with +, -, * and / operations.
- Language of string over {0, 1} where the string has unequal number of 0’s and 1’s.
Answer
Sign in to view the complete answer paper.
Show that the following grammar is not an SLR(1) grammar by constructing the SLR parsing table.
L → *R | id
R → L
Answer
Sign in to view the complete answer paper.
Construct Canonical LR parsing table for the following grammar. Show the actions of the parser for the string abab.
A → bAb | a
Answer
Sign in to view the complete answer paper.
Describe function overloading with an example.
Answer
Sign in to view the complete answer paper.
Compare static type checking and dynamic type checking.
Answer
Sign in to view the complete answer paper.
Write down the features of context sensitive languages.
Answer
Sign in to view the complete answer paper.
What do you understand by Code Optimization? Write the algorithm to partition the 3-address code into basic blocks.
Answer
Sign in to view the complete answer paper.
State and explain the issues in code generation process? Explain in detail.
Answer
Sign in to view the complete answer paper.
Construct the DAG for the basic block with following code:
Answer
Sign in to view the complete answer paper.