a presention on regular expression and regular expression to nfa
name:priyanka manna
roll no:12000121056
PAPER NAME : compiler design
paper code : pcc-cs 501
SEMESTER: 5th sem
dr. b. c roy engineering college, Durgapur-713206
department of computer science & engineering
(affiliated to maulana abul kalam azad university of technology )
• Introduction
• Languages associated with Regular
agenda Expression
• Identities for Regular Expression
• Properties of Regular Expression
• Arden’s Theorem
• Conversion of Regular expression
to NFA
• Conclusion
INTRODUCTION
The language accepted by finite automata can be easily described by simple
expressions called Regular Expressions. It is combination of dot(.),star(*),parenthesis
and plus(+).
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.
Let Σ be a given alphabets then φ, λ, a∈ Σ are all regular expressions.These are called
primitive regular expression.
If r1 and r2 are all regular expression then r1+r2, r1r2, r1* and(r1) are also regular
expression.
LANGUAGE ASSOCIATED WITH REGULAR EXPRESSION
Let r be regular expression then L(r) denoted by language associated with regular expression.
It is defined by the following rules
•Φ is regular expression ,denoting the empty set.
•λ is a regular expression, denoting { λ }.
•For every a∈ Σ ,a is a regular expression ,denoting { a }.
•If r1 and r2 are regular expression then L(r1 + r2)= L(r1) + L(r2).
•L(r1.r2) = L(r1).L(r2)
•L((r1)) = L(r1)
•L(r1*) = (L(r1))*
identities of REGULAR EXPRESSION
Let P,R,Q are regular expression then identities rule are
εR=R
ε*= ε Where, ε is null string
(Φ)*= ε Where,Φ is empty string
Φ.R=R.Φ= Φ
Φ+R = R
R+R = R
RR* = R*R = R+
(R*)* = R*
ε + RR* = R*
(P+Q)R = PR+QR
(P+Q)*= (P*Q*)* = (P*+Q*)*
R*(ε+R)=( ε+R)R*= R*
(R+ε)*= R*
ARDEN’S THEOREM
Let P and Q be two regular expression.P does not contain λ then the following equation
in R that is R= Q + RP has a unique solution given by R = QP*
PROPERTIES FOR REGULAR EXPRESSION
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 is a regular
expression whose language is (L ∩ M).
Kleene Closure:
R, S is a regular expression whose language is L, M. R* is a regular expression whose
language is L*.
Positive Closure:
R,S is a regular expression whose language is L, M.R+ is a regular expression whose language
is L+.
Complement:
The complement of regular expression is also regular expression.
REGULAR EXPRESSION to nfa
An NDFA is represented by digraphs called state diagram
•The vertices represent the states.
• The arcs labeled with an input alphabet show the transitions.
• The initial state is denoted by an empty single incoming arc.
• The final state is indicated by double circles.
Example:1
Design a NFA from given regular expression (ab)*ab*
Step 1:
ab b
q0 a qf
Step 2:
q1
a b
b
q0 a qf
Example:2
Design a NFA from given regular expression (a+ba)*ba
Step 1:
a+ba
b a
q0 q1 qf
Step 2:
a
b a qf
q0 q1
ba
Step 3:
a
q0 b a qf
q1
a
b
q2
conclusion
Regular expressions are a compact textual representation of a set of
strings representing a language.Regular expressions appeared as
Type-3 languages in Chomsky’s hierarchy.The class of regular
languages is a proper subset of the context-free languages.Any
Regular expression can be automatically compiled into an NFA,to a
DFA, and to a unique minimum-state DFA.
