Question Bank on Unit-4 of Automata & Compiler Design

  

Push Down Automata &
Turing Machine (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

8) 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 parsers: 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 →

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.

Continue reading →