Automata Theory and Compiler Design Past Paper PDF Dec 2023/Jan 2024

## CBCS SCHEME USN 1ME21CS017 21CS51 Fifth Semester B.E. Degree Examination, Dec.2023/Jan.2024 Automata Theory and Compiler Design Time: 3 hrs. Max. Marks: 100 ***Note: Answer any FIVE full questions, choosing ONE full question from each module.*** ### Module-1 **1.** a. Define the following...

## CBCS SCHEME USN 1ME21CS017 21CS51 Fifth Semester B.E. Degree Examination, Dec.2023/Jan.2024 Automata Theory and Compiler Design Time: 3 hrs. Max. Marks: 100 ***Note: Answer any FIVE full questions, choosing ONE full question from each module.*** ### Module-1 **1.** a. Define the following terms: * String * Language * Alphabet * Length of string b. Explain the various phases of compiler with neat diagram. c. Define DFA and design a DFA to accept the following language: * To accept strings having even number of a's and odd number of b's. * To accept strings of a's and b's not having the substring aab. **OR** **2.** a. Design the equivalent DFA to the following e-NFA. b. Minimize the following DFA by identifying distinguishable and non-distinguishable states. c. With neat diagram explain the components of language processing system in detail. ### Module-2 **3.** a. Define Regular Expressions. Write a regular expressions for the following: * L = {a^nb^m | n+m is even} * The set of all strings whose 3rd symbol from right end is 0 * L = {a^2b^2m | n ≥ 0, m ≥ 0} b. Convert the following automata to a regular expression. c. Explain the concept of input buffering in the Lexical Analysis along with sentinels. **OR** **4.** a. State and prove Pumping Lemma for regular languages and also prove the language L = {a^nb^m | n ≥ 0} is not a regular. ### Module-3 **5.** a. Define CFG. Write a CFG to the following languages. * All strings over {a, b} that are even and odd Palindromes. * L = {a^n | n ≥ 0}. b. Define ambiguity. Consider the grammar E→ E+E | E*E | (E) | id. Construct the leftmost and rightmost derivation, parse tree for the string id + id + id. Also show that the grammar is ambiguous. **OR** **6.** Consider the CFG given below with the production set, compute the following for the same. * First() and Follow() set * Predictive Parsing table Grammar is, E→TE' E'→+TE' |∈ T→FT' T'→FT' |∈ F→(E) | id b. Write an algorithm to eliminate lift recursion from a grammar. Also eliminate left recursion from the grammar. S→ Aalb A→ Ac | Sd |∈ ### Module-4 **7.** a. Define PDA. Design PDA for the language L = {WCWR | W ∈ (a, b)} and also show the Instaneous Description (ID) for the input aabCbaa. b. Construct LR(0) automata for the grammar given below. S → L | R L→ *Rid R → L **OR** **8.** a. Define shift reduce Parser and Handle. Also list and explain the different actions operations available in Bottom up parser. b. Construct the LR(1) automata for the given grammar. S→AA A→aAb ### Module-5 **9.** a. Design a Turing machine to accept the language L = {0^n1^2^n | n ≥1} b. Write a short note on the following: * Post correspondence problem * Design issues in code generation. **OR** **10.** a. Translate the arithmetic expression a = b * -c + b * -c into: * Three address code * Quadruple * Triple b. Write a short note on: * Decidable language * Halting problems in Turing machines. 2 of 2