Automata Theory

1
Which of the following is true-
   Φ = empty language           € = empty string
   


A. Φ = { € }
B. Φ ‡ { € }
C. Φ is not defined
D. € is not defined.

2
The set strings of 0's and 1's with atmost one pair consecutive one's-


A. (0+1)*(01)(10)(0+1)*
B. (0+1)*(01)*(10)(0+1)*
C. (0+1)*(01)(10)*(0+1)*
D. (0+!)(01)*(10)*(0+1)

3
Chomsky normal forms are not useful in-


A. elimination of useless symbols
B. elimination of transitive dependencies
C. elimination of a‚¬ productions
D. elimination of unit productions

4
Which of the following will be used for text searching application-


A. NFA
B. DFA
C. PDA
D. None of these

5
Which of the following languages is regular-


A. 0n10n
B. 0n | n is a power of 2
C. the set of strings 0i1j such that GCD of i and j is equal to one.
D. none of these