Question

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

Answer 1

ANSWER :

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:

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.

1.b)

10 smallest possible strings :

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

THANK YOU : )

PLEASE UPVOTE IT'S NEEDEDDD PLEASE