Assignments on Automata Theory & Compiler Design

 

Assignment Questions on ATCD

Assignment-1 Questions

Set-1:

Q1.  Consider the following NFA and answer the following:

        a) Give all the strings of length three or less accepted by the automaton.
        b) Convert the automaton to a DFA.

Q2. Construct an NFA and a DFA for recognizing the language denoted by the regular expression aa* + bb* 

Q3.  Write regular expressions for the following languages over the alphabet {0, 1}:
        a) The set of all strings that begin with 110.
        b) The set of all strings that contain 1011.
        c) The set of strings of 0's and 1's with at most one pair of consecutive 1's.

Q.4) The following productions define the grammar of the language consisting of all strings of even length:
        S --> AS | ε
        A --> aa | ab | ba | bb

Give leftmost and rightmost derivations of the following strings:
        a) aabbba
        b) baabab
        c) aaabbb

Q.5)

Set-2:

Q1.  Consider the following ε-NFA and do the following:

        a) Compute the ε-closure of each state.
        b) Give all the strings of length three or less accepted by the automaton.
        c) Convert the automaton to a DFA.

Q2.  Write regular expressions for the given language over the alphabet {a, b}:
        a) The set of strings containing at least one a and at least one b .

Q3.  Convert the following regular expressions to NFA's with ε -transitions.

Q.4) Consider the CFG G defined by productions:
                S --> aSbS | bSaS | ε
        Prove that L(G) is the set of all strings with an equal number of a's and b's

Q.5)

Assignment-2 Questions

Set-1:

Q1.  Define token.  Explain how finite automata is used to recognize tokens in a program?

Q2. Recognize the LEX tools available for compiler construction with an example.

Q3. What is LEX?  Explain the importance of LEX tool with an example.

Q4. Write the structure and syntax of LEX - Lexical Analyzer Generator.

Q5. Compare and contrast compiler writing from scratch with that of automating it using a scanner generator like LEX (Lexical Analyzer Generators)

Q6. Consider the following conditional statement:

            if (x > 3) then y=5 else y=10;

Explain how does a lexical analyzer help in analyzing the above statement during compilation?

Set-2:

Q1.  What is Parsing?  What role does the parser play in the overall compilation process?

Q2. Define CFG.  What is the role of CFG in compiler construction?

Q3. Explain the translation process at each stage of compiler for the given expression d:=b+c*60

Q4. Construct the syntax tree to evaluate the expression 2+3*4 through SDD.

Q5. Given a CFG, construct an equivalent PDA.

Grammar: S → aSb | ε

Detail the steps and transitions in the PDA.