Total language tree, Regular Grammar

<< Polish Notation (o-o-o)

Null Production >>

Theory of Automata

(CS402)

Theory of Automata

Lecture N0. 34

Reading Material

Introduction to Computer Theory

Chapter 12,13

Summary

Example of Ambiguous Grammar, Example of Unambiguous Grammer (PALINDROME), Total Language tree

with examples (Finite and infinite trees), Regular Grammar, FA to CFG, Semi word and Word, Theorem,

Defining Regular Grammar, Method to build TG for Regular Grammar

Example

Consider the following CFG

S Æ aS | bS | aaS | L

It can be observed that the word aaa can be derived from more than one production trees. Thus, the above CFG

is ambiguous. This ambiguity can be removed by removing the production S Æ aaS

Example

Consider the CFG of the language PALINDROME

SÆaSa|bSb|a|b|L

It may be noted that this CFG is unambiguous as all the words of the language PALINDROME can only be

generated by a unique production tree.

It may be noted that if the production S Æ aaSaa is added to the given CFG, the CFG thus obtained will be no

more unambiguous.

Total language tree

For a given CFG, a tree with the start symbol S as its root and whose nodes are working strings of terminals and

non-terminals. The descendants of each node are all possible results of applying every production to the working

string. This tree is called total language tree.

Example

Consider the following CFG

S Æ aa|bX|aXX

X Æ ab|b

then the total language tree for the given CFG may be

aXX

aXb

abb

abX

bab

aabb

aabX

aXab

abb

abab

aabb

aabab

abab

aabab

It may be observed from the above total language tree that dropping the repeated words, the language generated

by the given CFG is {aa, bab, bb, aabab, aabb, abab, abb}

Example

Consider the following CFG

S Æ X|b, X Æ aX

then following will be the total language tree of the above CFG

101

Theory of Automata

(CS402)

Note: It is to be

noted that the

only word in

aaX

this language

is b.

∂

aaa ...aX

Regular Grammar

All regular languages can be generated by CFGs. Some nonregular languages can be generated by CFGs but not

all possible languages can be generated by CFG, e.g. the CFG S Æ aSb|ab generates the language

{anbn:n=1,2,3, ...}, which is nonregular.

Note: It is to be noted that for every FA, there exists a CFG that generates the language accepted by this FA.

Example

Consider the language L expressed by (a+b)*aa(a+b)* i.e.the language of strings, defined over Â ={a,b},

containing aa. To construct the CFG corresponding to L, consider the FA accepting L, as follows

a,b

B+

S-

CFG corresponding to the above FA may be

S Æ bS|aA

A Æ aB|bS

B Æ aB|bB|L

It may be noted that the number of terminals in above CFG is equal to the number of states of corresponding FA

where the nonterminal S corresponds to the initial state and each transition defines a production.

Semiword

A semiword is a string of terminals (may be none) concatenated with exactly one nonterminal on the right i.e. a

semiword, in general, is of the following form

(terminal)(terminal)... (terminal)(nonterminal)

word

A word is a string of terminals. L is also a word.

Theorem

If every production in a CFG is one of the following forms

Nonterminal Æ semiword

Nonterminal Æ word

then the language generated by that CFG is regular.

Regular grammar

Definition

A CFG is said to be a regular grammar if it generates the regular language i.e. a CFG is said to be a regular

grammar in which each production is one of the two forms

Nonterminal Æ semiword

Nonterminal Æ word

102

Theory of Automata

(CS402)

Examples

The CFG S Æ aaS|bbS|L is a regular grammar. It may be observed that the above CFG generates the language

of strings expressed by the RE (aa+bb)*.

The CFG S Æ aA|bB, A Æ aS|a, B Æ bS|b is a regular grammar. It may be observed that the above CFG

generates the language of strings expressed by RE (aa+bb)+.

Following is a method of building TG corresponding to the regular grammar.

TG for Regular Grammar

For every regular grammar there exists a TG corresponding to the regular grammar.

Following is the method to build a TG from the given regular grammar

Define the states, of the required TG, equal in number to that of nonterminals of the given regular grammar. An

additional state is also defined to be the final state. The initial state should correspond to the nonterminal S.

For every production of the given regular grammar, there are two possibilities for the transitions of the required

If the production is of the form nonterminal Æ semiword, then transition of the required TG would start from the

state corresponding to the nonterminal on the left side of the production and would end in the state

corresponding to the nonterminal on the right side of the production, labeled by string of terminals in semiword.

If the production is of the form nonterminal Æ word, then transition of the TG would start from the state

corresponding to nonterminal on the left side of the production and would end on the final state of the TG,

labeled by the word.

Example

Consider the following CFG

S Æ aaS|bbS| L

The TG accepting the language generated by the above CFG is given below

S-

The corresponding RE may be (aa+bb)*.

103

Table of Contents: