BCA III Sem

Unit No. 2

Theory of Computation

Centre for Distance and Online Education

 Unit No. 2

2 – Regular Expressions,
Regular Grammar And
Languages
Centre for Distance and Online Education
Objectives
After completing this session, you will be able to:

 Define Regular Expression

 Define Regular Grammar

 Define closure properties of RL

 Define Pumping Lemma

Centre for Distance and Online Education

Regular Expression

• The language accepted by finite automata can be easily described by simple expressions called

Regular Expressions.

• It is the most effective way to represent any language.

• The languages accepted by some regular expression are referred to as Regular languages.

• A regular expression can also be described as a sequence of pattern that defines a string.

• Regular expressions are used to match character combinations in strings.

• String searching algorithm used this pattern to find the operations on a string.

Centre for Distance and Online Education

• For instance:
• In a regular expression, x* means zero or more occurrence of x. It
can generate {e, x, xx, xxx, xxxx, .....}
• In a regular expression, x+ means one or more occurrence of x. It can
generate {x, xx, xxx, xxxx, .....}
Operations on Regular Language

• Union: If L and M are two regular languages then their union L U M

is also a union.
• L U M = {s | s is in L or s is in M}
• Intersection: If L and M are two regular languages then their
intersection is also an intersection.
• L ⋂ M = {st | s is in L and t is in M}
• Kleen closure: If L is a regular language then its Kleen closure L1*
will also be a regular language.
• L* = Zero or more occurrence of language L.
1. Write the regular expression for the language accepting all
combinations of a's, over the set ∑ = {a}
• Solution: {ε, a, aa, aaa, ....}
• R = a*
2. Write the regular expression for the language accepting all
combinations of a's except the null string, over the set ∑ = {a}
Solution: L = {a, aa, aaa, ....}
R = a+
3.Write the regular expression for the language accepting all the string
containing any number of a's and b's.
Solution: L = {ε, a, aa, b, bb, ab, ba, aba, bab, .....}
r.e. = (a + b)*

4. Write the regular expression for the language accepting all the string
which are starting with 1 and ending with 0, over ∑ = {0, 1}.
Solution : R = 1 (0+1)* 0
5. Write the regular expression for the language accepting all the string
in which any number of a's is followed by any number of b's is
followed by any number of c's.
Solution: R = a* b* c*

6. Write the regular expression for the language over ∑ = {0} having
even length of the string.
• Solution: L = {ε, 00, 0000, 000000, ......}
• R = (00)*
Identities for regular expression –
• There are many identities for the regular expression. Let p, q and r are regular expressions.
• ∅+r=r
• ∅.r= r.∅ = ∅
• ∈.r = r.∈ =r
• ∈* = ∈ and ∅* = ∈
• r+r=r
• r*.r* = r*
• r.r* = r*.r = r+.
• (r*)* = r*
• ∈ +r.r* = r* = ∈ + r.r*
• (p.q)*.p = p.(q.p)*
• (p + q)* = (p*.q*)* = (p* + q*)*
• (p+ q).r= p.r+ q.r and r.(p+q) = r.p + r.q
Regular grammar
• Regular grammar is a type of grammar that describes a regular language.
• A regular grammar is a mathematical object, G, which consists of four
components, G = (V, T, P, S), where
• V: non-empty, finite set of non-terminal/variable symbols,
• T: a finite set of terminal symbols, or alphabet, symbols,
• P: a set of grammar rules, each of one having one of the forms
• A ⇢ aB
• A⇢ a
• A ⇢∈, Here ∈=empty string, A, B ∈ N, a ∈ ∑
• S ∈ N is the start symbol.
Regular grammar

• Type-3 grammar/regular grammar:

• Regular grammar generates regular language. They have a single
non-terminal on the left-hand side and a right-hand side consisting
of a single terminal or single terminal followed by a non-terminal.
• The productions must be in the form:
• A ⇢ xB
• A⇢x
• A ⇢ Bx
• where A, B ∈ Variable(V) and x ∈ T* i.e. string of terminals.
Types of regular grammar:

• Left Linear grammar(LLG)

• Right linear grammar(RLG)
1. Left linear grammar(LLG):
•
In LLG, the productions are in the form if all the productions are of
the form
• A ⇢ Bx
• A⇢x
• where A,B ∈ V and x ∈ T*
2. Right linear grammar(RLG):
•
In RLG, the productions are in the form if all the productions are of
the form
• A ⇢ xB
• A⇢x
• where A,B ∈ V and x ∈ T*
Regular Grammar and Finite Automata
• Example: FA for accepting strings that start with b

• ∑ = {a,b}
• Initial state(q0) = A
• Final state(F) = B
• The RLG corresponding to FA is
• A ⇢ bB
• B ⇢ ∈/aB/bB
• The above grammar is RLG, which can be written directly through
FA.
• For converting the RLG into LLG for language L, the following
procedure needs to be followed:
• Step 1: Reverse the FA for language L
• Step 2: Write the RLG for it.
• Step 3: Reverse the right linear grammar.
• after this we get the grammar that generates the language that
represents the LLG for the same language L.
• L=set of all strings over input symbols a and b which start with b.
We are converting it into LLG.
• Step1: The reversal of FA is

• Step 2: The corresponding RLG for this reversed FA is

• B ⇢ aB/bB/bA
• A⇢∈
• Step 3: The reversing the above RLG we get
• B ⇢ Ba/Bb/Ab
• A⇢∈
• So this is LLG for language L( which represents all strings that start
with b).
L= {b, ba, bb, baa, bab ,bba, bbb ….. }
Conversion of RLG (Right linear grammar) to FA (Finite automata):

• Start state: The first production state is known as the start state.
• Final state: All the states which end up with terminals without
following any further non-terminal.
• Example:
• In this example, we have the right linear grammar for language L. This
grammar shows all the strings which end with 0.
• X → 0X / 1Y / 0Y
• Y→∈
• So the finite automata which correspond to right linear grammar are
described as follows:
• Here we will begin with variable X and use its production like this:
• The production X → 0X means that when the transition gets '0' as an
input symbol, then state transition will always remain in the same state X.
• The production X → 1Y means that when the transition gets '1' as an
input symbol, then the state transition will go to state Y from state X.
• The production X → 0Y means that when the transition gets '0' as an
input symbol, then the state transition will go to state Y from state X.
• The production Y → ∈ means that this state does not require any type of
state transitions. In the corresponding FA (finite automata), this type of
production would be the final state because its RHS is terminal.
• So for the corresponding right linear grammar, the final NFA
(nonfinite automat) is described as follows:

• Conversion of LLG to FA:

Conversion of LLG into RLG

• To explain this, we will take the above grammar, which is used to

represent the language L, and accept all sets of strings that begin
with variable y. The left linear grammar for this grammar is
described as follows:
• Y → Yx / Yy / Xy
• X→∈
• Step 1:
• In this step, we will convert the LLG into FA. There is the same
process of conversion as described above. So
• Step 2:
• In this step, we will reverse the FA. That means we will convert the
initial state into the final state and the final state into starting state.
We will also reverse all the edges like this:
• Step 3:
• In this step, we will write RLG corresponding to reversed finite
automata.
• X → yY
• Y → xY/yY/ ∈
Closure properties of Regular languages

• Closure properties on regular languages are defined as certain

operations on regular language which are guaranteed to produce
regular language.
• Closure refers to some operation on a language, resulting in a new
language that is of same “type” as originally operated on i.e.,
regular.
• Regular languages are closed under following operations
• Consider L and M are regular languages:
• Kleen Closure: RS is a regular expression whose language is L, M. R*
is a regular expression whose language is L*.
• Positive closure: RS is a regular expression whose language is L,
M. R+ is a regular expression whose language is L+.
• Complement: The complement of a language L (with respect to an
alphabet E such that E* contains L) is E*–L. Since E*is surely regular,
the complement of a regular language is always regular.
• Reverse Operator: Given language L, LR is the set of strings whose
reversal is in L.
• Example: L = {0, 01, 100}; LR={0, 10, 001}.
• Proof: Let E be a regular expression for L. We show how to reverse
E, to provide a regular expression ER for LR.
• Union: Let L and M be the languages of regular expressions R and S,
respectively.Then R+S is a regular expression whose language is(L U
M).
• Intersection: Let L and M be the languages of regular expressions R and
S, respectively then it a regular expression whose language is L
intersection M.
• proof: Let A and B be DFA’s whose languages are L and M, respectively.
Construct C, the product automaton of A and B make the final states of
C be the pairs consisting of final states of both A and B.
• Set Difference operator: If L and M are regular languages, then so is L –
M = strings in L but not M.
• Proof: Let A and B be DFA’s whose languages are L and M, respectively.
Construct C, the product automaton of A and B make the final states of
C be the pairs, where A-state is final but B-state is not.
• Homomorphism: A homomorphism on an alphabet is a function
that gives a string for each symbol in that alphabet.
• Example: h(0) = ab; h(1) = E. Extend to strings by h(a1…an) =h(a1)…
h(an). Example: h(01010) = ababab. If L is a regular language, and h
is a homomorphism on its alphabet, then h(L)= {h(w) | w is in L} is
also a regular language.
• Proof: Let E be a regular expression for L. Apply h to each symbol in
E. Language of resulting R, E is h(L).
• Inverse Homomorphism : Let h be a homomorphism and L a
language whose alphabet is the output language of h.
• (L) = {w | h(w) is in L}.
Pumping lemma for regular language

• There are two Pumping Lemmas (PL), which are defined for Regular
Languages and Context - Free Languages.
• Pumping lemma for Regular languages
• It gives a method for pumping (generating) many substrings from a
given string.
• In other words, we say it provides means to break a given long input
string into several substrings.
• Lt gives necessary condition(s) to prove a set of strings is not regular.
Theorem

• For any regular language L, there exists an integer P, such that for all
w in L
• |w|>=P
• We can break w into three strings, w=xyz such that.
• (1)lxyl < P
• (2)lyl > 1
• (3)for all k>= 0: the string xykz is also in L
Application of pumping lemma

• Pumping lemma is to be applied to show that certain languages are

not regular.
• It should never be used to show a language is regular.
• If L is regular, it satisfies the Pumping lemma.
• If L does not satisfy the Pumping Lemma, it is not regular.
• Steps to prove that a language is not regular by using PLare as follows−
• step 1 − We have to assume that L is regular
• step 2 − So, the pumping lemma should hold for L.
• step 3 − It has to have a pumping length (say P).
• step 4 − All strings longer that P can be pumped |w|>=p.
• step 5 − Now find a string 'w' in L such that |w|>=P
• step 6 − Divide w into xyz.
• step 7 − Show that xyiz ∉ L for some i.
• step 8 − Then consider all ways that w can be divided into xyz.
• step 9 − Show that none of these can satisfy all the 3 pumping conditions at same time.
• step 10 − w cannot be pumped = CONTRADICTION.
•
Summary
•The language accepted by finite automata can be easily described by simple
expressions called Regular Expressions Identities of regular expression

•Regular grammar is a type of grammar that describes a regular language.

•Closure properties on regular languages are defined as certain operations on

regular language which are guaranteed to produce regular language.

•There are two Pumping Lemmas (PL), which are defined for Regular
Languages and Context - Free Languages

Centre for Distance and Online Education

Additional Resources
1. John C. martin, “Introduction to Language and Theory of Computation”, TMH,
Third Edition. 978-0-07-066048-9.
2. Michel Sipser “Introduction to Theory of Computation” Thomson Course
Technology, Second Edition 0-534-95097-3.
3. Kavi Mahesh, “Theory of Computation” Wiley-India, ISBN : 978-81-265-3311-
4
4. HopcroftUlman, “Introduction To Automata Theory, Languages And
Computations”, Pearson Education Asia, 2nd Edition
5. Daniel I.A. Cohen, “Introduction to Computer Theory” Wiley-India, ISBN: 978-
81-265-1334-5
6. E V Krishnamurthy, “Introduction to Theory of Computer Science”, EWP
Second 2nd Edition.
7. . K.L.P Mishra, N. Chandrasekaran, “ Theory Of Computer Science (Automata,
Languages and Computation)”, Prentice Hall India, 2nd Edition
Centre for Distance and Online Education
Any Questions ?

Centre for Distance and Online Education

Thank You!
The title of the college here along
with a brief description if required

Centre for Distance and Online Education