THEORY OF COMPUTATION
Subject Code : BCS503
Faculty : Dr. J. Anvar Shathik
Module - II
01
Regular Expression
Regular Expression
• Regular Expression is a simple expression used to describe the language accepted by the Finite
Automata.
• The language accepted by finite automata can easily described by the simple expression called
“Regular Expression”
• It is an effective way to represent any language
• The langue accepted by some regular expression are referred as “ Regular Languages “
• Regular Expression can also be described as a sequence of pattern that defines a string .
• It is used to represent certain set of strings in an algebraic fashion
, ℇ,
02
• Symbols we use 0, 1, a, b,
Regular Expression
Regular Expression
• Regular Expression x* means zero or more occurrences of x
• Regular Expression x+ means one or more occurrences of x
Operations of Regular Language
• Union of two Regular Expression is also Regular Expression
• Concatenation of two Regular Expression is also Regular Expression
• Closure of Regular Expression is also Regular Expression
02
Regular Expression
02
Applications of Regular Expression
1) Lexical Analysis:
• Task of lexical analyzer is to scan the input and separate out the tokens.
• Example : Identifier is a category of token in the source code and it can be identified by Regular
Expression. (letter) (letter + digit)*
2) Finding the Pattern in the String
• Regular expression is used to find the pattern in the given text from pdf, doc file or any document.
• Example : Strings end with digits is a pattern in the given text which can be recognized by the
following Regular Expression [ a – 3 A – Z]* [ 0 – 9 ] +
02
Applications of Regular Expression
3) Search Commands in Unix
• In Unix egrep is a command used for searching text pattern in the file and list of words containing that
pattern
• Example : Assume the file xyz having the following data
• Ram , Dexter , Raman, Jhon
• % egrep ‘n’ xyz this will search all owrds in file xyz having letter n
• Output : Raman, John
02
Applications of Regular Expression
02
Finite Automata and Regular Expression
02
Finite Automata and Regular Expression
Converting Finite Automata into Regular Expression
STEP 1: Initial state should not have incoming Edge. If exist create one new state and make it as the
initial state
• q0 having incoming edge. So create new state and make it as a initial state . So that we can remove in
coming edge
02
Finite Automata and Regular Expression
Converting Finite Automata into Regular Expression
STEP 2: Finite state machine should not have multiple final states. If exist then create one or more new
states and make this state as the final state and show epsilon transition from old final state to new final
state
02
Finite Automata and Regular Expression
Converting Finite Automata into Regular Expression
STEP 3: Final state in Finite state machine should not have outgoing edge. If exist then create new
state and make it as the final state
02
Finite Automata and Regular Expression
Converting Finite Automata into
Regular Expression
STEP 4: Remove every state one after
other in any order and at the same time
write equivalent Regular expression.
• Finally Finite Automata should have
one initial state and one final state .
• 02
Building FSM fromRegular Expression
• Any Language that can defined by regular expression can be accepted by some Finite state machine
• According to kleen’s theorem 1
For every regular expression there is an equivalent FSM.
02
Building FSM fromRegular Expression
02
Building FSM fromRegular Expression
02
Closure properties of Regular Expression
02
Closure properties of Regular Expression
02
Closure properties of Regular Expression
02
Closure properties of Regular Expression
Closure under Union, Concatenation and Kleen Star
Proof: It is given that L1 and L2 are Regular Languages , there exist s regular expression R1 and R2
such that
L1= L (R1) , L2= L(R2)
By the definition of regular expressions we have
• R1 + R2 is a regular expression denoting the language L1 U L2
• R1R2 is a regular expression denoting the language L1. L2
• R1* is a regular expression denoting the language L1 *
• So that regular language are closed under Union, Concatenation and Kleen Star
02
Closure properties of Regular Expression
Closure under Union, Concatenation and Kleen Star
Proof: It is given that L1 and L2 are Regular Languages , there exist s regular expression R1 and R2
such that
L1= L (R1) , L2= L(R2)
By the definition of regular expressions we have
• R1 + R2 is a regular expression denoting the language L1 U L2
• R1R2 is a regular expression denoting the language L1. L2
• R1* is a regular expression denoting the language L1 *
• So that regular language are closed under Union, Concatenation and Kleen Star
02
Closure properties of Regular Expression
Closure under Complement
02
Closure properties of Regular Expression
Closure under Intersection
• If L and M are Regular Languages. Intersection is given by
• There must be FA accepting
02
Closure properties of Regular Expression
Closure under Difference
02
Closure properties of Regular Expression
Closure under Reverse
02
Pumping Lema for Regular Expression
• If L is a regular language represented with an Automata with a maximum number of states ‘ n’ then
there is word in L such that the length |z| >= n. Further we may write z = xyz in such a way that |xy|
<= n, |y| >=1
• xyqz in L where q is a constatnt
Pumping Lema
• For showing certain languages not to be regular
02
Pumping Lema for Regular Expression
• Theorem
02
Pumping Lema for Regular Expression
Steps :
• Assume L is regular
• Apply Pumping theorem for the given language
• Choose s string w, where w belongs to L and | w | >= K
• Split w into xyz such that | xy | <=k , y
• Choose a value for q such that xyqz is not in L
• Our Assumption is wrong and hence the given linguae is not regular
02
64