TOC UNIT II - CFC

Let G=(V, T, P, S)

where a production can be written as:

S->aAS|a

A->SbA|ba|SS

Which of the following string is produced by the grammar?

• aabbaa

• aabbaab

• baabab

• None of the mentioned

Simplify the given grammar:

A-> a| aaA| abBc

B-> abba| b

• A-> a| aaA| ababbAc| abbc, B-> abba|b

• A-> a| aaA| abbc, B->abba

• None of the mentioned

• A-> a| aaA| ababbAc| abbc

For the given Regular expression, the minimum number of variables including starting variable required to derive its grammar is:

(011+1)*(01)*

• 4

• 6

• 3

• 5

The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is

• 3

• 6

• 7

• 5

The entity which generate Language is termed as:

• Grammar

• Automata

• Data

• Tokens

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

• L is a set of string with odd number of 0

• L is a set of binary complement

• L is a set of 0ⁿ1ⁿ

• L is a set of numbers divisible by 2

For the given Regular expression, the minimum number of terminals required to derive its grammar is:

(011+1)*(01)*

• 4

• 6

• 3

• 5

Which among the following is the correct grammar for the given language?

L={x∈{0,1}*|number of zeroes in x¹number of one’s in x}

• S-> 1|0S|0SS|SS0|S0S

• S-> 0|0S|1SS|SS1|S1S

• None of the mentioned

• S-> 0|SS|1SS|SS1|S1S

The context free grammar S → SS | 0S1 | 1S0 | ɛ generates

• Unequal number of 0’s and 1’s

• Equal number of 0’s and 1’s

• Any number of 0’s followed by any number of 1’s

• None of these

Given:

S->aSb

S->e

S-> A

A->aA

B->C

C->D

The ratio of number of useless variables to number of useless production is:

• 3/4

• 2/3

• 1

• 0