TOC quiz

Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)* ?

• The set of all strings containing the substring 00.

• The set of all strings containing at most two 0’s.

• The set of all strings containing at least two 0’s.

• The set of all strings that begin and end with either 0 or 1.

Which one of the following is FALSE?

• There is unique minimal DFA for every regular language

• Every NFA can be converted to an equivalent PDA.

• Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Which of the following are regular sets?

• {aⁿb^2m|n≥0, m≥0}

• {aⁿb^m | n = 2m}

• {aⁿb^m n=m}

Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

• 3

• 4

• 5

• 9

The language recognized by M is :

• {w ∈ {a, b}* / every a in w is followed by ex­actly two b's}

• {w ∈ {a, b}* every a in w is followed by at least two b’}

• {w ∈ {a, b}* w contains the substring 'abb'}

• {w ∈ {a, b}* w does not contain 'aa' as a substring}

• {q0, q1, q2}

• {q0, q1}

• {q0, q1, q2, q3}

• {q3}

The smallest finite automation which accepts the language {x | length of x is divisible by 3} has :

• 2 states

• 3 states

• 4 states

• 5 states

• Only S1 is correct

• Only S2 is correct

• both

• none

S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

• All palindromes

• All odd length palindromes.

• Strings that begin and end with the same symbol

• All even length palindromes

Which of these languages are deterministic Context-free languages?

• Only L1

• Only L1 and L2

• All the three languages

• None