Frequently Asked Questions (FAQ)

1.  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}.

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

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

4.  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.  Construct NFA over the alphabet Σ={a,b} for the language having a set of strings formed using either 101 or 110 as substring.

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

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

8.  How many states will the DFA equivalent of NFA with n states have in the worst case? Justify.

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

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