Mathematical Foundation of Computer Science

DHARM

280 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Hence we say that if,

α 1 ⇒α 2 ⇒α 3 ⇒ .........αn–1 ⇒αn

then,α 1 ⇒N αn or α 1 derives α 2 in some finite steps.

Example 11.2. A grammar G is defined over VN = {S, A}, VT = {0, 1}, start symbol is S and
following productions are in set P:
P = {S → 0S, A → 1S,
S → 0A, A → 0,
A → 0A, S → 1};
Sol. These productions can also be written as:
S → 0S/1A/1
A → 0A/1S/0
Above grammar is a Type-3 grammar/regular grammar hence there exist a finite au-
tomaton (shown in Fig. 11.1) that accepts the L(G).

S A

1

1

(^00)
Fig. 11.1
Construction of Finite Automata is very easy. All nonterminals in the grammar are
corresponding to the states of finite automata. From starting state S an arc labeled 0 returns
itself because S derives 0S. Similarly an arc labeled 1 goes to state A due to production S
derives 1A and so on.
Now at what state automata stop. We see the production S → 1A and S → 1 are only
possible if A is a stopping state. (Fig. 11.2)
S A
1
1
(^00)
Fig. 11.2
The strings that are in L(G) are constructed as follows:
S ⇒ 1;
S ⇒ 0S ⇒ 01;
S ⇒ 0S ⇒ 00S ⇒ 001;
S ⇒ 0S ⇒ 00S ⇒ 001A ⇒ 0010/0010A/0011S and similarly derivedother
strings.
Example 11.3. A grammar G is defined over VN = {a}, VT = {S}, S is the starting symbol and
productions are:
S → aaaa/aaaaS