Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 323

A

B

S

Self loop on A

Fig. 11.30
The directed graph of A → AB has self loop on symbol A so there exist a cycle. Hence, L(G)
is infinite.
Consider another example of grammar G
S → AB | a
A → a
B → b
The directed graph of above grammar (Fig. 11.31) has no cycle. Hence L(G) is finite.

A

B

S

Fig. 11.31
Now we study above following general cases i.e.,
Case I
Suppose the graph has a cycle which causes due to following vertices arrangement in the
directed graph,
X 0 , X 1 , X 2 , .................. Xn, X 0.
Since all vertices are connected through arcs. So there is an arc from X 0 to X 1 with
possible production X 0 → X 1 A or X 0 → BX 1.
So, X 0 ⇒ α 1 X 1 β 1 where α 1 and α 1 are ∈ VN and | α 1 β 1 | = 1 and for next arc from X 1 to X 2
possible production X 1 → X 2 A or X 1 → BX 2.
So, X 0 ⇒ α 1 X 1 β 1 ⇒ α 2 X 2 β 2 where α 2 and α 2 ∈ VN and | α 2 β 2 | = 2, and so on.
[where X 0 ⇒ a 1 X 1 b 1 means
⇒ AX 1
(∵ X 0 ⇒ AX 1 is the defined prodn. Here α 1 is A and β 1 is nothing so | α 1 β 1 | is 1)
⇒ AX 2 B