Regular Grammar

A grammar is said to be regular, if the production is in the form -
A → αB,
A -> a,
A → ε,
for A, B ∈ N, a ∈ Σ, and ε the empty string
A regular grammar is a 4 tuple -
G = (V, Σ, P, S)
V - It is non-empty, finite set of non-terminal symbols,
Σ - finite set of terminal symbols, (Σ ∈ V),
P - a finite set of productions or rules,
S - start symbol, S ∈ (V - Σ)

1. Regular Grammar ( Theory of Computation)

2. A grammar is a 4-tuple G = (V,T,P,S)
V: set of variables or nonterminals
T: set of terminal symbols (terminals)
P: set of productions
S: a start symbol from V

3. V = { S }, T = { 0, 1 }
Productions:
S 
S 0S1
This grammar
represents strings
such as:
0011
000111
01


4. Leftmost derivation: the leftmost variable is
always the one replaced when applying a
production
Rightmost derivation: rightmost variable is
replaced

5. A tree in graph theory is a set of nodes such
that
›There is a special node called the root
›Nodes can have zero or more child nodes
›Nodes without children are called leaves
›Interior nodes: nodes that are not leaves
A parse tree for a grammar G is a tree such that
the interior nodes are non-terminals in G and
children of a non-terminal correspond to the
body of a production in G

6. Yield: concatenation of leaves from left to
right
If the root of the tree is the start symbol, and
all leaves are terminal symbols, then the
yield is a string in L(G)
Note: a derivation always corresponds to
some parse tree

7. Regular Language –Regular Language are
those languages which are accepted by finite
automaton.
Regular Expression –Regular Expression
are used to denote Regular Languages.
Regular Set –Any set that represent the
value of Regular Expression.

8. In order to find out a regular expression of a
finite automaton we use Arden's theorem.
Statement 1 -Let P & Q be two regular
expression.
Statement 2 –If P doesn’t contain null string,
then R = Q + R P ( has a unique solution)
i.e. , R= Q P*

9. R = Q + R P
R = Q + ( Q + R P ) P
R = Q + Q P + R P 2
R = Q + Q P + ( Q + R P ) P 2
R = Q + Q P + Q P 2+ R P 3
R = Q ( Ф+ P + P 2+ _ _ _ ) + R P n+ 1
R = Q ( P * ) + R P n + 1
R = Q P * + R P n + 1

10. Union of two regular language are always be regular.
Intersection of two regular language are always be
regular.
Complement of two regular language are always be
regular.
Difference of two regular language are always be
regular.
Kleenclosure operation over a regular language
always be a regular.

11. Concatenation of two regular language are
always be regular.
Reverse of two regular language are always
be regular.

12. Pumping Lemma is used as a proof for
irregularity of a language. Thus, if a
language is regular, it always satisfies
pumping lemma. If there exists at least one
string made from pumping which is not in L,
then L is surely not regular.

13. The opposite of this may not always be true.
That is, if Pumping Lemma holds, it does not
mean that the language is regular.

14. It always consist of three variables i.e., x, y,
I, z.
Where, X can be null or can hold value
y can not be null and has a value in it.
I is the power upon y which increment by
step .
Z can be null or can hold value .

15. x y z
Ф aa Ф
wxyiz i>0
Ф(aa)iФ= (aa)I
aaФL i=1
aaaФL i=2