Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 281

Then L (G) contains following strings:

S ⇒ aaaa;

S ⇒ aaaaS ⇒ aaaa aaaa;

S ⇒ aaaaS ⇒ aaaa aaaaS ⇒ aaaa aaaa aaaa; and so on.

Hence L(G) = {multiple of 4a’s}

11.4 Sentential Form...............................................................................................................

For any grammar all derivation starts from S, where S is the starting symbol. If S drive x(∈ VT)

in finite steps i.e.,

S ⇒N x and if α 1 , α 2 , α 3 ,......are some intermediate derivatives that are in (VN ∪ VT)*

then,

S ⇒α 1 ⇒α 2 ⇒α 3 ⇒......⇒αn ⇒ x

This sequence of derivations is called sentential form.

Left sentential form

If S ⇒N x by means of means of deriving leftmost nonterminal symbol first then the sequence

of derivations is called left sentential form.

Right sentential form

If S ⇒N x by means of deriving rightmost nonterminal symbol first then the sequence of deriva-

tion is called right sentential form.
Lemma 11.1
(∈) is not in the language of Type-1 grammar.
Proof. Since we know that if grammar is type-1 then its productions α → β fulfill the restric-
tions:
l α must have at least single nonterminal, and
l | β | ≥ | α |
Now if A → ε is any production of this grammar then it’s fulfill previous restriction but,
because ε says zero occurrences of symbols so, | ε | = 0. Hence it does it, fulfill the next
restriction.
Hence we conclude the proof.
Theorem 11.1. If L is a regular language then there exists a type-3 grammar G, i.e.,
L = L (G).
Proof. Since L is regular, hence there exists a DFA that accepts it. ......
Let DFA M is defined as,
M = (Q, Σ, δ, q 0 , F) where all tuples has their usual meaning.
Now the theorem says, from the DFA we can construct a type-3 grammar G i.e.,
L = L (G).
Assume that grammar G is defined as,
G = (VN, VT, S, P) where tuples have been related with the tuples of M like as,
l All states (∈ Q) will be in the set of non terminals, s.t. VN = Q.
l All input symbols (∈ Σ) will be the variables, s.t. VT = Σ.