Consider the grammar : S —> ABCc | Abc BA —> AB Bb —> bb Ab —> ab Aa —> aa Which of the following sentences can be derived by this 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
15

Theory of Computation MCQ with Answers

15) Consider the grammar :
S —> ABCc | Abc
BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa
Which of the following sentences can be derived by this grammar

abc

aab

abcc

abbb

Answer is:

abc

Theory of Computation MCQ with Answers

For more MCQ's Click Here

16) Pumping lemma is generally used for proving that

given grammar is regular

given grammar is not regular

whether two given regular expressions are equivalent or not

None of these

Answer is:

given grammar is not regular

17) The language of all words with at least 2 a's can be described by the regular expression

(ab)*a and a (ba)*

(a + b)* ab* a (a + b)*

b* ab* a (a + b)*

all of these

Answer is:

all of these

Explanation:

The language of all words with at least 2 a's can be described by the regular expression
(ab)*a and a (ba)*
(a + b)* ab* a (a + b)*
b* ab* a (a + b)*

18) Any string of terminals that can be generated by the following CFG is
S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a

has atleast one ′b ′

should end in a ′a ′

has no consecutive a ′s or b ′s

has atleast two a ′s

Answer is:

has atleast two a ′s

19) L = (an bn an| n = 1,2,3) is an example of a language that is

context free

not context free

not context free but whose complement is CF

both 1) not context free and 2) not context free but whose complement is CF

Answer is:

both 1) not context free and 2) not context free but whose complement is CF

Theory of Computation MCQ with Answers

For more MCQ's Click Here

15) Consider the grammar : S —> ABCc | Abc BA —> AB Bb —> bb Ab —> ab Aa —> aa Which of the following sentences can be derived by this grammar

abc

Theory of Computation MCQ with Answers

Related Theory of Computation MCQ with Answers

16) Pumping lemma is generally used for proving that

given grammar is not regular

17) The language of all words with at least 2 a's can be described by the regular expression

all of these

18) Any string of terminals that can be generated by the following CFG is S-> XY X--> aX | bX | a Y-> Ya | Yb | a

has atleast two a ′s

19) L = (an bn an| n = 1,2,3) is an example of a language that is

both 1) not context free and 2) not context free but whose complement is CF

Theory of Computation MCQ with Answers

15) Consider the grammar :
S —> ABCc | Abc
BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa
Which of the following sentences can be derived by this grammar

18) Any string of terminals that can be generated by the following CFG is
S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a