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