Regular Expressions Notes | EduRev

Created by: Renu Garg

: Regular Expressions Notes | EduRev

 Page 1


1
CS 172:  Computability and Complexity
Regular Expressions
Sanjit A. Seshia
EECS, UC Berkeley
Acknowledgments: L.von Ahn, L. Blum, M. Blum
S. A. Seshia 2
The Picture So Far
DFA NFA
Regular
language
Page 2


1
CS 172:  Computability and Complexity
Regular Expressions
Sanjit A. Seshia
EECS, UC Berkeley
Acknowledgments: L.von Ahn, L. Blum, M. Blum
S. A. Seshia 2
The Picture So Far
DFA NFA
Regular
language
2
S. A. Seshia 3
Today’s Lecture
DFA NFA
Regular
language
Regular
expression
S. A. Seshia 4
Regular Expressions
• What is a regular expression?
Page 3


1
CS 172:  Computability and Complexity
Regular Expressions
Sanjit A. Seshia
EECS, UC Berkeley
Acknowledgments: L.von Ahn, L. Blum, M. Blum
S. A. Seshia 2
The Picture So Far
DFA NFA
Regular
language
2
S. A. Seshia 3
Today’s Lecture
DFA NFA
Regular
language
Regular
expression
S. A. Seshia 4
Regular Expressions
• What is a regular expression?
3
S. A. Seshia 5
Regular Expressions
• Q. What is a regular expression?
• A. It’s a “textual”/ “algebraic”
representation of a regular language
– A DFA can be viewed as a “pictorial” / 
“explicit” representation
• We will prove that a regular expressions 
(regexps) indeed represent regular languages 
S. A. Seshia 6
s is a regular expression representing {s s s s}
( s s s s ? ? ? ? S S S S )
e is a regular expression representing {e}
Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø
If R
1
and R
2
are regular expressions 
representing L
1
and L
2
then:
(R
1
R
2
) represents L
1
· ·· ·L
2
(R
1 
? ? ? ? R
2
) represents L
1 
? ? ? ? L
2
(R
1
)* represents L
1
*
Regular Expressions: Definition
Page 4


1
CS 172:  Computability and Complexity
Regular Expressions
Sanjit A. Seshia
EECS, UC Berkeley
Acknowledgments: L.von Ahn, L. Blum, M. Blum
S. A. Seshia 2
The Picture So Far
DFA NFA
Regular
language
2
S. A. Seshia 3
Today’s Lecture
DFA NFA
Regular
language
Regular
expression
S. A. Seshia 4
Regular Expressions
• What is a regular expression?
3
S. A. Seshia 5
Regular Expressions
• Q. What is a regular expression?
• A. It’s a “textual”/ “algebraic”
representation of a regular language
– A DFA can be viewed as a “pictorial” / 
“explicit” representation
• We will prove that a regular expressions 
(regexps) indeed represent regular languages 
S. A. Seshia 6
s is a regular expression representing {s s s s}
( s s s s ? ? ? ? S S S S )
e is a regular expression representing {e}
Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø
If R
1
and R
2
are regular expressions 
representing L
1
and L
2
then:
(R
1
R
2
) represents L
1
· ·· ·L
2
(R
1 
? ? ? ? R
2
) represents L
1 
? ? ? ? L
2
(R
1
)* represents L
1
*
Regular Expressions: Definition
4
S. A. Seshia 7
* * * *
····
? ? ? ?
Operator Precedence
1.
2.
3.
( often left out; 
a · · · · b  ab )
S. A. Seshia 8
R
2
R
1
* ( R
1
*R
2
? ? ? ? R
3
= ( ) )? ? ? ? R
3
Example of Precedence
Page 5


1
CS 172:  Computability and Complexity
Regular Expressions
Sanjit A. Seshia
EECS, UC Berkeley
Acknowledgments: L.von Ahn, L. Blum, M. Blum
S. A. Seshia 2
The Picture So Far
DFA NFA
Regular
language
2
S. A. Seshia 3
Today’s Lecture
DFA NFA
Regular
language
Regular
expression
S. A. Seshia 4
Regular Expressions
• What is a regular expression?
3
S. A. Seshia 5
Regular Expressions
• Q. What is a regular expression?
• A. It’s a “textual”/ “algebraic”
representation of a regular language
– A DFA can be viewed as a “pictorial” / 
“explicit” representation
• We will prove that a regular expressions 
(regexps) indeed represent regular languages 
S. A. Seshia 6
s is a regular expression representing {s s s s}
( s s s s ? ? ? ? S S S S )
e is a regular expression representing {e}
Ø Ø Ø Ø is a regular expression representing Ø Ø Ø Ø
If R
1
and R
2
are regular expressions 
representing L
1
and L
2
then:
(R
1
R
2
) represents L
1
· ·· ·L
2
(R
1 
? ? ? ? R
2
) represents L
1 
? ? ? ? L
2
(R
1
)* represents L
1
*
Regular Expressions: Definition
4
S. A. Seshia 7
* * * *
····
? ? ? ?
Operator Precedence
1.
2.
3.
( often left out; 
a · · · · b  ab )
S. A. Seshia 8
R
2
R
1
* ( R
1
*R
2
? ? ? ? R
3
= ( ) )? ? ? ? R
3
Example of Precedence
5
S. A. Seshia 9
{ w | w has exactly a single 1 } 
0*10*
What’s the regexp?
S. A. Seshia 10
What language does 
Ø Ø Ø Ø
*  
represent?
{e}
Read More