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
43

Theory of Computation MCQ with Answers

43) Which of the following statements is (are) correct ?

Recursive languages are closed under complementation.

If a language and its complement are both regular, the language is recursive

Set of recursively enumerable language is closed under union

All of these

Answer is:

All of these

Theory of Computation MCQ with Answers

For more MCQ's Click Here

44) Which of the following statement is wrong ?

Any regular language has an equivalent context-free grammar.

Some non-regular languages can’t be generated by any context-free grammar

Intersection of context free language and a regular language is always context-free

All languages can be generated by context- free grammar

Answer is:

All languages can be generated by context- free grammar

45) Consider a grammar : G = ( { x , y ) , { s , x , y } , p , s) where elements of parse :
S--> x y
S -->y x
x--> x z
x--> x
y--> y
z--> z
The language L generated by G most accurately is called

Chomsky type 0

Chomsky type 1

Chomsky type 2

Chomsky type 3

Answer is:

Chomsky type 3

46) Consider a grammar : G = { { S } , { 0 , 1 } , p , s } where elements of p are:
S --> ss
S--> 0S1
S--> 1S0
S--> empty
The grammar will generate

regular language

context-free language

context-sensitive language

recursive enumerable language

Answer is:

regular language

47) A grammar that produces more than one parse tree for some sentence is called

ambiguous

unambiguous

regular

none of these

Answer is:

ambiguous

Theory of Computation MCQ with Answers

For more MCQ's Click Here

43) Which of the following statements is (are) correct ?

All of these

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

44) Which of the following statement is wrong ?

All languages can be generated by context- free grammar

45) Consider a grammar : G = ( { x , y ) , { s , x , y } , p , s) where elements of parse : S--> x y S -->y x x--> x z x--> x y--> y z--> z The language L generated by G most accurately is called

Chomsky type 3

46) Consider a grammar : G = { { S } , { 0 , 1 } , p , s } where elements of p are: S --> ss S--> 0S1 S--> 1S0 S--> empty The grammar will generate

regular language

47) A grammar that produces more than one parse tree for some sentence is called

ambiguous

Theory of Computation MCQ with Answers

45) Consider a grammar : G = ( { x , y ) , { s , x , y } , p , s) where elements of parse :
S--> x y
S -->y x
x--> x z
x--> x
y--> y
z--> z
The language L generated by G most accurately is called

46) Consider a grammar : G = { { S } , { 0 , 1 } , p , s } where elements of p are:
S --> ss
S--> 0S1
S--> 1S0
S--> empty
The grammar will generate