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
41

Theory of Computation MCQ with Answers

41) For which of the following application, regular expressions can not be used ?

Designing computers

Designing compilers

Both 1) Designing computers and 2) Designing compilers

Developing computers

Answer is:

Both 1) Designing computers and 2) Designing compilers

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

xwy + xw * xy + ywx

xw * y + xw x yx + ywx

xw xy + xww * y + ywx

Answer is:

xw * y + xw * yx + ywx

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

Theory of Computation MCQ with Answers

For more MCQ's Click Here

41) For which of the following application, regular expressions can not be used ?

Both 1) Designing computers and 2) Designing compilers

Theory of Computation MCQ with Answers

Related 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

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

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