Question Bank on Unit-5 of Automata & Compiler Design

 

Analysis & Synthesis Process
of Compilation (Unit-5)

Multiple Choice Questions (MCQ)

1) Three-Address Code is called “Three Address” because:

        (i)    Each instruction can have atmost three operators 

        (ii)   Each instruction can have atmost three addresses (operands)

        (iii)  Each instruction can have exactly three operators

        (iv)  Each instruction can have exactly three addresses (operands)

2) The main advantage of generating Intermediate Code in a compiler is that:

        (i)    It allows better optimization independant of machine architecture

        (ii)   It eliminates the need for lexical analysis

        (iii)  It directly increases the run-time speed of the compiler

        (iv)  It reduces the number of syntax errors

3) Consider the expression a = b + c * d

A possible three-address code sequence is:

        (i)    t1 = b + c; a = t1 * d

        (ii)   t1 = c * d; a = b + t1

        (iii)  a = b + c * d

        (iv)  t1 = b * c; a = t1 + d

4) Which of the following techniques allows the compiler to fill in the address of forward jumps later (as the destinations of jump instructions are not known immediate) during intermedia code generation?

        (i)    Peephole Optimization

        (ii)   Backpatching

        (iii)  Register Allocation

        (iv)  Code Scheduling

5) Consider the following statements:

S1: A three-address code instruction contains at most three addresses

S2: The process of backpatching is used to know the forward jump addresses in control flow statements

Choose the correct optionn

        (i)   Only S1 is true         (ii)   Only S2 is true         (iii)  Both S1 and S2 are true         (iv)  Neither S1 nor S2 is true

6) Consider the following three-address code:

If a < b goto L1
t1 = a + b
L1: t2 = a * b

Which of the following is incorrect regarding the flow control in the code?         (i)    The expression will jump to L1 if a < b         (ii)   The addition t1 = a+b will execute when a >= b         (iii)  The multiplication t2 = a * b will execute only if a < b         (iv)  The multiplication t2 = a * b will always execute

7) Which of the following is NOT a task of the code generation phase of a compiler

        (i)    Instruction selection

        (ii)   Register allocation

        (iii)  Syntax analysis

        (iv)  Instruction ordering

8) In most modern compilers, the code generation phase takes which of the following as the input?

        (i)    The original source program

        (ii)   Intermediate code and information from the symbol table

        (iii)  Only the syntax tree

        (iv)  Target machine instruction

9) During a procedure call, which of the following actions are performed by the calling function (caller) before transferring the program control to the called function?           (i)    Evaluating actual arguments         (ii)   Passing parameters to the called function         (iii)  Saving necessary machine state such as return address         (iv)  All of the above

10) When the called function finishes execution, which component is used to determine where execution should resume in the calling function?         (i)    Control Link         (ii)   Access Link         (iii)  Return Address         (iv)  Local Variables

Descriptive Questions

Q1.    What is the runtime environment and what role does it play in program execution?

Q2.    Write three address code for the expression : 
            a+b*c – d /e

Q3.    Distinguish Syntax Directed Definition and Syntax Directed Translation?

Q4.    Discuss about various storage allocation strategies in runtime environment?

Q5.    Explain about different storage allocation strategies. 

Q6.    Compare and contrast the three main runtime storage organization techniques: static allocation, stack allocation, and heap allocation.

Q7.    Write the comparison among Static allocation, Stack allocation and Heap Allocation with their merits and limitations.

Q8.    Define Loop unrolling and Loop jamming? Also explain constant folding? 

Q9.    Define Three Address Codes. Outline various Three Address code representations for the expression:
            x + - y * (- y + z)

Q10.  Explain the procedure to translate Control Statements into Three address code with example.

Q11.  Explain the Code optimization techniques with example.

Q12.  Describe Register Allocation. Briefly explain the strategies available for register allocation and assignment.

Q13.  Explain the various issues in the design of code generation.

Q14.  Define object code generation and describe its importance in the compilation process. 

Continue reading →

Question Bank on Unit-4 of Automata & Compiler Design

  

Introduction to Compilers &
Lexical Analysis (Unit-4)

Multiple Choice Questions (MCQ)

1) A Symbol Table in a Compiler is mainly used to:

        (i) Store Keywords

        (ii) Store Identifiers and their Attributes

        (iii) Generate Machine Code

        (iv) Perform Lexical Analysis

2) When can semantic errors be detected?

        (i) During Compile Time

        (ii) During Run Time

        (iii) Both (i) and (ii)

        (iv) None of the above

3) Which of the following mechanism is used to associate meaning (semantic information) with a Context Free Grammar (CFG)?

        (i) Syntax Directed Definition

        (ii) Parse Table

        (iii) Left Recursion

        (iv) Token Stream

4) Symbol Tables are mainly used during which phase of Compilation?

        (i) Syntax Analysis

        (ii) Semantic Analysis

        (iii) Code Generation

        (iv) Code Optimization

5) Which Data Structure is commonly used to implement a Symbol Table?

        (i) Queue (ii) Stack 

        (iii) Hash Table (iv) Tree

6) Which of the following are stored in a Symbol Table?

        (i) Variable Name (ii) Data Type

        (iii) Memory Location (iv) All the above

7) Average expected lookup time for a given key in a hash-table based Symbol Table is:

        (i) O(log n)

        (ii) O(n)

        (iii) O(1)

        (iv) None of the above

Descriptive Questions

Q1.  Explain different steps involved in a typical language processing system with a neat diagram.

Q2.  Identify the difference between compiler & assembler. Retrieve the phases of a typical compiler?

Q3.  Tabulating the difference between lexemes, patterns  and tokens. How do you recognize tokens in Lexical Analysis?

Q4.  Define token? Explain how Finite automata is used to recognize tokens in a program?

Q5.  List out the phases of compiler? What is the role of lexical analysis in constructing a compiler? 

Q6.  Explain the concept of a “pass” in compiler design. How do multiple passes contribute to the overall translation process?

Q7.  Discuss the contents and structure of a symbol table. What types of information are stored for each identifier?

Q8.  What is a symbol table. What role does the parser play in the overall compilation process? 

Q9.  Consider the following Conditional statement:
                if (x > 3) then y = 5 else y = 10;

        Explain how does a lexical analyzer help the above statement in the process of compilation?

Q10.  Recognize the LEX tools available for compiler constrction with an example.

Q11.  Write the structure and syntax of LEX-Lexical Analyzer Generators.

Q12.  Compare and contrast compiler writing from scratch with using a scanner generator like LEX (Lexical Analyzer Generator).

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

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

Q15.  Briefly describe the two main classifications of parser: top-down and bottom-up parsing. 

Q16.  Draw the syntax tree for the following expression: 
                (a+(b*c)^d-e)/(f+g) 

Q17.  Construct Syntax tree to evaluate the expression 2+3*4, through SDD.

Q18.  Construct LALR parser for the following grammar: 
                S-->CC         C-->aC         C-->d

Q19.  Construct a LALR parsing table for the grammar:
                S-->Aa | bAc | dc | bda A-->a 

Continue reading →

Question Bank on Unit-3 of Automata Theory

 

Push Down Automata &
Turing Machine (Unit-3)

Descriptive Questions

Q1.  What are undecidable problems? Explain with example.

Q2.  Define Recursively Enumerable Language. 

Q3.  Define NP hard and NP completeness problem.

Q4.  Define CFG and what is the importance of it in compiler construction? 

Q5.  List the components of a Turing Machine. State Universal Turing Machine. 

Q6.  Construct Turing machine for the languages containing the set of all strings of balanced paranthesis?

Q7.  Explain the different types of Turing Machine.

Q8.   Give an overview of recursively enumerable language.

Q9.  Given a CFG, construct an equivalent PDA.

            Grammar: S → aSb | ε

        Detail the steps and transitions in the PDA.

Q10. Explain about Halting Problem of Turing machine.

Continue reading →

Question Bank on Unit-2 of Automata Theory

Regular Expression & CFG (Unit-2)

Multiple Choice Questions (MCQ)

1) 

2) From the following regular expressions over an alphabet {a, b} given below, which can yield all the possible strings over ∑ (a, b)?

3)  Which regular expression best describe the language accepted by the non-deterministic automaton below?

4) What is the Regular Expression (RE) over the alphabet Σ={a,b} for the language that indicate the strings containing "ab" as substrings?

        (A) (a+b)ab(a+b)
        (B) (a+b)*ab(a+b)
        (C) (ab)*ab(ab)*
        (D) ab(a+b)*

5)  Consider the FA shown in the figure given below, where ‘-’ is the start sate and ‘+’ is the ending state.  The language accepted by the FA is

6)  Which regular expression best describe the language accepted by the non-deterministic automaton below?

7)

8) From the following regular expressions over an alphabet {a, b} given below, which can yield all the possible strings over ∑ (a, b)?

9) Which of the following options are correct for the given DFA:

(A) 0(10)*

(B) (01)*0

(C) Both (A) and (B)

(D) Neither (A) nor (B)

10) 

11) Pumping lemma is generally used for proving which of the following:

(A) A given grammar is regular

(B) A given grammar is non-regular

(C) Whether two given regular expression are equivalent or not

(D) Both (A) and (C)

12) If G is a grammar with productions
            S → SaS | aSb | bSa | SS |∈

Where S is the start variable, then which one of the following strings is not generated by G?

(A)    abab
(B)    aaab
(C)    abbaa
(D)    babba

Solution:

Thus, the string which is not generated by the given grammar G is babba

13) Identify the language generated by the following grammar, where S is the start variable.
        S → XY
        X → aX|a
        Y → aYb|∈

14) If a grammar G has three productions:

S --> aSa | bSb | c

then which of the following strings are part of the language recognized by CFG?

(A)    abcba & bacab
(B)    abcba & abcab
(C)    acca & bcccb
(D)    acccb & bccca

Solution:

The language defined by the given grammar is odd length palindrome formed using alphabets {a, b} with c as the middle alphabet.

Thus, option (A) is the correct answer.

15) Sentence that can be generated from the following production grammar is:

Descriptive Questions

Q1.  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.

Q2.  Write regular expressions over the alphabet {a, b} for recognizing a 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) 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:
        i) aabbba
        ii) baabab
        iii) aaabbb

Q.5)

Q.6) 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.7)

Q.8) Consider the following grammar:
        S --> A1B
        A --> 0A | ε
        B --> 0B | 1B | ε

Give leftmost and rightmost derivations of the following strings:
        a) 00101
        b) 1001
        c) 00011

Solution:

Q.9) 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.10) 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.11) Find a derivation tree of a*b+a*b 
        given that a*b+a*b is in L(G), where G is defined as follows:

        S --> S + S | S* S, S --> a | b

Q.12) Consider the following productions: 
        S --> aB | bA
        A --> aS | bAA | a
        B --> bS | aBB | b

For the strings aaabbabbba, find:
        a) the leftmost derivation
        b) the rightmost derivation and
        c) the parse tree.

Q.13)  Illustrate the construction of Non Deterministic Finite Automata for the Regular Expression: (a+b)*a

Q.14) Construct the regular expression for the language over the set S={0,1} that can have a set of all strings containing no three consecutive 0’s.

Q.15)  Construct a CFG to generate the binary strings that are Palindromes ex: 010, 00100, 101, 11011

Q.16)  Identify the language generated by the following CFG: S-->Aab; A-->Aab|b

Continue reading →

Question Bank on Unit-1 of Automata Theory

 Automata & Its Types (Unit-1)

Multiple Choice Questions (MCQ)

1) Finite state machine can recognize which of the following languages:

       (A) Only context-free grammar

       (B) Only regular grammar

       (C) Any unambiguous grammar

       (D) Any grammar

2)  Which of the following statements about ε-moves (epsilon transitions) in Finite Automata is correct?

       (A) An ε-move consumes one input symbol from the alphabet

       (B) ε-moves are allowed only in DFA

       (C) ε-moves allow the automaton to change states without consuming any input symbol

       (D) An automaton with ε-move always accepts all input strings

3)

       (A) Regular Language

       (B) Context-Sensitive Language

       (C) Context-Free Language

       (D) Phrase-Structure Language

4) The language, L is defined over Σ = {0, 1, 2, 3, 4, 5, 6, 7} has the following set of strings included in its dictionary:

L = {7, 16, 43, 61, 223, ...} 

Identify the language represented by L from the following options:

       (A) Alternate odd and even numbers

       (B) Octal representation of a number

       (C) Divisible by 7

       (D) Octal representation of a number divisible by 7.

5) Consider the given finite automaton and identify the Language recognized by it:

        (A) A DFA that accepts all strings that end with "ba"

        (B) A DFA that accepts all strings that end with "a"

        (C) A DFA that accepts all strings that end with "b"

        (D) A DFA that accepts all strings that end with "ab"

6)  In the automaton below, s is the start state and t is only final state.

7)  The below transition diagram of a finite automaton accepts which of the following set of strings?

8)  For the given NFA which of the following is the equivalent DFA:

9)  ‘Every NFA can be simulated by a DFA’. The statement is true/false?

10) How many states will the DFA equivalent of NFA with n states have in the worst case?

 

        (A) n

        (B) 2n

        (C) 2ⁿ

        (D) n²

11) Two finite state machines are said to be equivalent if they:

 

        (A) Have the same number of edges

        (B) Have the same number of states

        (C) Recognise the same set of tokens

        (D) Have the same number of edges and states

12)  Given the language L = {ab, aa, baa}, which of the following strings are in L*? 
        1) abaabaaabaa 
        2) aaaabaaaa 
        3) baaaaabaaaab 
        4) baaaaabaa 

Possible Answers:

        (A) 1, 2 and 3 
        (B) 2, 3 and 4 
        (C) 1, 2 and 4 
        (D) 1, 3 and 4 

Descriptive Questions

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.  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.

Q4. Construct NFA for the language: 

L= {w|w is in the form of ‘x01y’ for some strings x and y consisting of 0’s and 1’s}

Q5.  Draw the transition diagram for an NFA which accepts all strings with two consecutive 0’s

Q6.  Constructure the Finite Automata from the following 5-tuple notation:

Q7.  Construct NFA over the alphabet Σ={a,b} for the language having a set of strings formed using either 101 or 110 as substring.

Q8) Draw the ε-NFA and compute the ε-closure of each state for the given NFA. Also identify the subsets of starting state in DFA.

Solution:

Q9)  Constructure the Finite Automata using 5-tuple notation for the recognizing a set of strings that can have 1 followed immediately by 00

Continue reading →