Test Your Knowledge on Regular Expressions

Multiple Choice Questions on RE & CFG 

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

Q2. 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)*

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

Q4.  Which regular expression best describe the language accepted by the non-deterministic automaton below?

Q5:

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

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

Q8. 

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

Q10. Sentence that can be generated from the following production grammar is:

Descriptive Questions on Regular Expressions

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

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

Q3.  Write regular expressions for the following languages over the alphabet {a, b}:

    a) The set of strings containing at least one a and at least one b .

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