Question

1. a) Rewrite the following rule base as a CFG and provide its formal definition ( S is the start

state )

S → aSb | bAA

A → b {aB} | a | Bc

B → aB | c

b) Generate the 10 smallest possible strings using the above rule base. ( from problem a)

2. Either show that the following strings are in this language or state why these strings can

not be..

S → AB | BC | cB

A → Ac | aBB | b

B → Cb | cBb | a

C → Ac | bCA | c

a) aCbcBbcBb b) ccbcbbb b) cabbCA

Answer 1

solution:

given data:

1).

a)

Context-free grammar

A context-free grammar is a formal grammar that is used to generate all possible strings in a given formal language.

Context-free grammar G can be defined by four tuples as:

1. G= (V/N, T, P, S)  

Where,

G describes the grammar

T describes a finite set of terminal symbols.

V/N describes a finite set of variables or non-terminal symbols

P describes a set of production rules

S is the start symbol.

In CFG, the start symbol is used to derive the string. You can derive the string by repeatedly replacing a non-terminal by the right-hand side of the production, until all non-terminal have been replaced by terminal symbols.

Example:

consider given productions are:

S → aSb | bAA

A → b {aB} | a | Bc

B → aB | c

Now check that abaccb string can be derived from the given CFG.

S →aSb

S →abAAb

S →abaAb

S →abaBcb

S →abaccb

By applying the production recursively and finally applying the production B → c, we get the string abaccb.

b)

10 smallest possible strings

= {baa, bacc, bcca, bcccc, abaab, baacc, abaccb, abccab, bccacc, bacccc }

please give me thumb up