www.ThinkITI.com

Home
MCQ
Search
Free Apps
Important
Study Groups
Contact Us
Policy

Home
MCQ
Objective Questions
Engineering
Computer Science
Computer Science Set-1
Theory of Computation
23

Theory of Computation MCQ with Answers

23) Which of the following statement is correct?

All languages can not be generated by CFG

Any regular language has an equivalent CFG

Some non regular languages can't be generated by CFG

both 1) Any regular language has an equivalent CFG and 2) Some non regular languages can't be generated by CFG

Answer is:

both 1) Any regular language has an equivalent CFG and 2) Some non regular languages can't be generated by CFG

Theory of Computation MCQ with Answers

For more MCQ's Click Here

Related Theory of Computation MCQ with Answers

24) Given A = (0,1) and L = A*. If R = (0n 1n, n > 0), then language L ∪R and R are respectively

regular, regular

not regular, regular

regular, not regular

context free, not regular

Answer is:

context free, not regular

25) Define for a context free language
L ≤{0 ; 1} init (L) = {u/uv ε L for some v in {0,1}}
(in other words, init (L) is the set of prefixes of L)
Let L {w/w is noempty and has an equal number of 0’s and 1’s)
Then init (L) is

set of all binary strings with unequal number of 0’s and 1’s

set of all binary strings including the null string

set of all binary strings with exactly one more 0’s than the number of 1’s or 1 more than the number of 0’s

none of these

Answer is:

set of all binary strings including the null string

26) If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?

L1L2

L1 ∩L2

L1 ∩R

L1 ∪L2

Answer is:

L1 ∩L2

27) Consider a grammar with the following productions
S--> aab | bac | aB
S --> αS | b
S --> αb b | ab
Sα --> bdb | b
The above grammar is

Context free

regular

context sensitive

LR ( k )

Answer is:

context sensitive

Theory of Computation MCQ with Answers

For more MCQ's Click Here