Problems on Context Free Grammar (CFG)

Test Your Knowledge on CFG

Multiple Choice Questions (MCQ):

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

Q.2) Identify the language generated by the following grammar, where S is the start variable.

S → XY

X → aX|a

Y → aYb|∈

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

Problems to Solve:

Q.4) The following grammar generates the language of regular expression 01(0+1):

S --> A1B

A --> 0A | ε

B --> 0B | 1B | ε

Give leftmost and rightmost derivations of the following strings:

a) 00101

b) 1001

c) 00011

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

Continue reading →

Mid-1 Exam QP on ACD (Solved)

Multiple Choice Questions (MCQ)

1.a) Finite state machine can recognize which of the following languges:

       (A) Only context-free grammar

       (B) Only regular grammar

       (C) Any unambiguous grammar

       (D) Any grammar

1.b)  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

1.c)

       (A) Regular Language

       (B) Context-Sensitive Language

       (C) Context-Free Language

       (D) Phrase-Structure Language

1.d) 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²

1.e) 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

1.f)

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

1.h) 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)

1.i) Sentence that can be generated from the following production grammar is:

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

Descriptive Questions

Solution for Mid-1 Questions

MCQs:

1.a) B

1.b) C

1.c) A

1.d) C

1.e) C

1.f) D

1.g) B

1.h) B

1.i) A

1.j) B

Problem Solving

2.b) 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}.

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

4.a)  Draw the transition diagram for NFA which accepts all strings with two consecutive 0’s

4.b) 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.

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

5.b) Draw the ε-NFA and compute the εclosure of each state. Identify the subsets of starting state in DFA.

Solution:

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

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

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

Continue reading →

Conversion of e-NFA to DFA

Problems Solved during Class Room Teaching

Problem 1:

Problem 2:

Continue reading →

Tutorial-2 on RE & CFG

Tutorial-2 on RE & CFG

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

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

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

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

Q5.  Construct the NFA for the regular expression r = ((01+10)*00)*

Q6. Constructure the Finite Automata using 5-tuple notation for the regular expression 1*01(0+11)*

Continue reading →

Tutorial-1 on Automata Theory

Tutorial-1 on Finite Automata

Q1.  For the given NFA which of the following is the equivalent DFA:

Q2.  Consider the following NFA and answer the following:

        a) Compute the ε-closure of each state.

        b) Convert the automaton to a DFA.

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

      a) Compute the ε-closure of each state.

      b) Convert the automaton to a DFA.

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

Q5.  Convert the given ε-NFA to its equivalent DFA:

Continue reading →

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.

Continue reading →