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
22

Theory of Computation MCQ with Answers

22) Set of regular languages over a given alphabet set is not closed under

union

complementation

intersection

All of these

Answer is:

All of these

Explanation:

Set of regular languages over a given alphabet set is not closed under
* union
* complementation
* intersection

Theory of Computation MCQ with Answers

For more MCQ's Click Here

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

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

Theory of Computation MCQ with Answers

For more MCQ's Click Here

22) Set of regular languages over a given alphabet set is not closed under

All of these

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

23) Which of the following statement is correct?

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

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

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 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?

L1 ∩L2

Theory of Computation MCQ with Answers

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