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?

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