Automata Theory

21.	Palindromes can’t be recognized by any FSA because FSA cannot remember arbitrarily large amount of information FSA cannot deterministically fix the midpoint Even if the mid point is known an FSA cannot find whether the second half of the string matches the first half all of the above
22.	Let Σ = {a, b, c, d, e}. The number of strings in Σ* of length 4 such that no symbol is used more than once in a string is 360 120 35 36
23.	Which of the following denotes Chomskian hiearchy? REG ⊂ CFL ⊂ CSL ⊂ type0 CFL ⊂ REG ⊂ type0 ⊂ CSL CSL ⊂ type0 ⊂ REG ⊂ CFL CSL ⊂ CFL ⊂ REG ⊂ type0
24.	A language L is accepted by a FSA iff it is CFL CSL recursive regular
25.	Which of the following regular expressions denotes a language comprising of all possible strings over Σ = {a, b} of length n where n is a multiple of 3. (a + b + aa + bb + aba + bba)* (aaa + bbb)* ((a + b)(a + b)(a + b))* (aaa + ab + a) + (bbb + bb + a)
26.	A language is represented by a regular expression (a)*(a + ba). Which of the following string does not belong to the regular set represented by the above expression. aaa aba ababa aa
27.	Which of the following is not primitive recursive but partially recursive? McCarthy’s function Riemann function Ackermann’s function Bounded function
28.	Consider the following right-linear grammar G = (N, T, P, S) N = {S} P : S → aS|aA T = {a, b} A → bA|b Which of the following regular expression denotes L(G)? (a + b)* a(ab)*b aa*bb* a*b*
29.	Which of the following strings is not generated by the following grammar? S → SaSbS|ε aabb abab aababb aaabb
30.	Consider the following NFSA The automaton accepts all words of the form {(ab)na|n ≥ 1} all words that end with a and ε all words that end with a and not ε all words containing substring ba Answers: 21. d 22. b 23. a 24. d 25. c 26. c 27. c 28. c 29. d 30. c
	Previous                 Next