Turing Machine MCQ Set-2

1. Which of the following statement is wrong?

a) Every recursive language is recursively enumerable

b) A language is accepted by FA if and only if it is context free

c) Recursive languages are closed under intersection

d) A language is accepted by FA if and only if it is right linear

2. Which of the following statement is true?

a) All languages can be generated by CFG

b) The number of symbols necessary to simulate a turing machine (TM) with m symbols and n states is mn

c) Any regular language has an equivalent CFG

d) The class of CFG is not closed under union

3. Recursively enumerable languages are not closed under

a) Complementation

b) Union

c) Intersection

d) none of these

4. Regular expression (x/y) (x/y) denotes the set

a) {x/y, x/y}

b) {xx, xy, yx, yy}

c) {x, y}

d) {x, y,xy}

5. Regular expression x/y denoted the set

a) {x,y}

b) {xy}

c) {x}

d) {y}

6. The regular expressions denote a language comprising all possible strings of even length over the alphabet (0, 1)

a) 1 + 0 (1 + 0)*

b) (0 + 1) (1 + 0)*

c) (1 + 0)

d) (00 + 0111 + 10)*

7. The regular expressions denote zero or more instances of an x or y is

a) (x + y)

b) (x + y)*

c) (x* + y)

d) (xy)*

8. The regular expression have all strings in which any number of 0's is followed by any number of 1's followed by any number of 2's is

a) (0 + 1 + 2)*

b) 0*1*2*

c) 0* + 1 + 2

d) (0 + 1)*2*

9. The regular expression have all strings of 0's and 1's with no two consecutive 0's, is

a) (0 + 1)

b) (0 + 1)*

c) (0 + ∈) (1 + 10)*

d) (0 + 1)* 011

10. The regular expression with all strings of 0's and 1's with at-least two consecutive 0's, is

a) 1 + (10)*

b) (0 + 1)*00 (0 + 1)*

c) (0 + 1)*011

d) 0*1*2*