Context Free Grammars Questions

MCQ bookmark_border

21.

Which of following statement(s) is/are not correct? (I) Languages generated by the grammar S?aSa ? aa is not regular. (II) Languages generated by the grammar S?aSb ? aa is not regular. (III) Languages generated by the grammar S?S1|S3, S1?aS1c |S2|?, S2?aS2b|?, S3?aS3b|S4| ?, S4?bS4c|? is {a^nb^mc^k | k = |n - m|, n?0, m?0, k?0}. (IV) Languages generated by the grammar S?S1S3, S1?aS1c |S2|?, S2?aS2b|?, S3?aS3b|S4| ?, S4?bS4c|? is {a^nb^mc^k | k = |n - m|, n?0, m?0, k?0}.

A

Only (II), (IV)

B

Only (I), (III), (IV)

C

Only (I), (II), (III)

D

All of the above

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

22.

Consider the following grammars G1 and G2 respectively. Grammar - G1:

A1 ? A2A3
A2 ? A3A1 | b
A3 ? A1A1 | a

Grammar - G2:

S ? AA | 0
A ? SS | 1

Consider the following statements regarding above grammars: (I): This grammar is not left recursive and equivalent to grammar - G1:

A1 ? A2A3
A2 ?  A3A1 | b
A3 ? a | bA3A1 | aK | bA3A1K 
k ? A1A3A1 | A1A3A1K

(II): This grammar is not left recursive and equivalent to grammar - G2:

S ? A A | 0
A ? 0S | 1 | 0SK | 1K
K ? AS | ASK

A

Only statement (I) is correct

B

Only statement (II) is correct

C

Both statements (I) and (II) are correct

D

Neither statement (I) not (II) is correct

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

23.

Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A ? ?, with |?| = k > 1. The derivation tree for any string W ? L (G) has a height such that

A

h<((|W| - 1)/k-1)

B

log_k|W| < h

C

log_k|W| < h < ((|W| - 1)/k-1)

D

log_k|W| <= h <= ((|W| - 1)/k-1)

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

24.

CFG (Context Free Grammar) is not closed under

A

Union

B

Complementation

C

Kleene star

D

Product

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

25.

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

A

2x - 1

B

2x

C

2x + 1

D

2^x

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

26.

The entity which generate Language is termed as:

A

Automata

B

Tokens

C

Grammar

D

Data

Correct Answer: C

The entity which accepts a language is termed as Automata while the one which generates it is called Grammar. Tokens are the smallest individual unit of a program.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

27.

Production Rule: aAb->agb belongs to which of the following category?

A

Regular Language

B

Context free Language

C

Context Sensitive Language

D

Recursively Ennumerable Language

Correct Answer: C

Context Sensitive Language or Type 1 or Linearly Bounded Non deterministic Language has the production rule where the production is context dependent i.e. aAb->agb.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

28.

Which of the following statement is false?

A

Context free language is the subset of context sensitive language

B

Regular language is the subset of context sensitive language

C

Recursively ennumerable language is the super set of regular language

D

Context sensitive language is a subset of context free language

Correct Answer: D

Every regular language can be produced by context free grammar and context free language can be produced by context sensitive grammar and so on. Find the context sensitive language from the given diagram

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

29.

The Grammar can be defined as: G=(V, ?, p, S)
In the given definition, what does S represents?

A

Accepting State

B

Starting Variable

C

Sensitive Grammar

D

None of these

Correct Answer: B

G=(V, ?, p, S), here V=Finite set of variables, ?= set of terminals, p= finite productions, S= Starting Variable.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

30.

Which among the following cannot be accepted by a regular grammar?

A

L is a set of numbers divisible by 2

B

L is a set of binary complement

C

L is a set of string with odd number of 0

D

L is a set of 0ⁿ1ⁿ

Correct Answer: D

There exists no finite automata to accept the given language i.e. 0n1n. For other options, it is possible to make a dfa or nfa representing the language set.

Check Answer report_problem Report forum Discussion