Regular Grammar,Regular Expressions and Regular Languages

We know that , a grammar is a set of rules and regulations for constructing a language. Grammar defines how strings are generated in a language.

In TOC, a Grammar is represented by four tuples.

G = { V_NT, V_T, P, S }

V_NT : Finite set of Non-terminal symbols

V_T : Finite set of terminal symbols

P : Set of Production Rules

S : Start symbol . It is the symbol from where strings are produced ). It is a subset of V_NT .

Terminal Symbols are represented by small case letters. (a,b,c…)

Non Terminal Symbols are represented by capital letters. (A,B,C…). These symbols take part in language generation but are not a part of it.

Production Rules – used to generate new sequences of strings and symbols. It is denoted in LHS to RHS pattern.

Regular Grammar

Regular grammars are those that generates regular languages. It consists of terminal symbols, non terminal symbols, start symbol and production rules. We know that the production rules are denoted in LHS to RHS pattern. In regular grammars, if the production rule is of the form 

x -> y,

then, x can be a set of non terminal symbols or a set of terminal symbol or combination of both and cannot be null. y can be a set of non-terminal symbols or a set of terminal symbols or combination of both and can be null. 

Example 1.  G = { |S|, |a|, | P: S->a,S->aS| , S }

In the above example, S is the non-terminal symbol and a is the terminal symbol. The production rules are 1) S->a , 2) S->aS. S is the start symbol and is a subset of V_NT. So , we start generating the language by the start symbol.

S

S->a   [ using production rule 1 ]

OR

S->aS   [ using production rule 2 ]

S->aaS  [ using production rule 2 ]

S->aaaS  [ using production rule 2 ]

S->aaaaS  [ using production rule 2 ]

In this situation , a can be replaced n number of times using production rule 2. Therefore , we can write the language that will be generated like ; L(G) = { aⁿ | n>=1 }, which also means that this grammar can be used to generate strings of the form (a)⁺ which defines the Positive Closure property.

Types of Regular Grammar – 

1.  Right Linear Grammar
2. Left Linear Grammar

• In Right Linear Grammar , the production rules are of the form, 

A -> aB or A -> a

Example – S -> aS | bS | ε

• In Left Linear Grammar, production rules are of the form 

A -> Ba or A -> a

Regular Expression

Regular expressions in Theory of Computation (TOC) are algebraic, symbolic notations used to define, represent, and recognize regular languages (patterns of strings) accepted by finite automata. It is a method of representing a language.

A regular expression R is defined over an alphabet Σ. It can include ε (empty string) , empty set or any symbols a ∈ Σ.

Regular Expressions represent Regular Language by the following rules – 

• ε ( epsilon) is a regular expression which denotes the language { ε }.
• ∅ is a regular expression denoting the empty set { }.
• For each symbol ‘a’ , if  a ∈ Σ, then it is a regular expression. 
• Union ( + or U ) – Union of two regular expression is also a regular expression. If a and b are two regular expression , then a + b is also a regular expression which represents the language {a,b}.
• Concatenation (.) – Concatenation of two regular expression is also a regular expression. If a and b are two regular expression , then ab is also a regular expression.
• Kleene Closure (*) – a* represents zero or more occurrences of  ‘a’, which is also a regular expression.