Consider the following grammar S --> Ax / By A --> By/Cw B --> x / Bw C--> y Which of the regular expressions describe the same set of strings as the grammar ?

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
42

Theory of Computation MCQ with Answers

42) Consider the following grammar
S --> Ax / By
A --> By/Cw
B --> x / Bw
C--> y
Which of the regular expressions describe the same set of strings as the grammar ?

xw * y + xw * yx + ywx

xwy + xw * xy + ywx

xw * y + xw x yx + ywx

xw xy + xww * y + ywx

Answer is:

xw * y + xw * yx + ywx

Theory of Computation MCQ with Answers

For more MCQ's Click Here

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

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

Theory of Computation MCQ with Answers

For more MCQ's Click Here

42) Consider the following grammar S --> Ax / By A --> By/Cw B --> x / Bw C--> y Which of the regular expressions describe the same set of strings as the grammar ?

xw * y + xw * yx + ywx

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

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

All of these

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

Theory of Computation MCQ with Answers

42) Consider the following grammar
S --> Ax / By
A --> By/Cw
B --> x / Bw
C--> y
Which of the regular expressions describe the same set of strings as the 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

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