PPT: Regular Expressions | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


1
Regular Expressions
Page 2


1
Regular Expressions
2
Regular Expressions vs. Finite
Automata
n Offers a declarative way to express the pattern of any
string we want to accept
n E.g., 01*+ 10*
n Automata => more machine-like
< input: string  , output: [accept/reject]  >
n Regular expressions => more program syntax-like
n Unix environments heavily use regular expressions
n E.g., bash shell, grep, vi & other editors, sed
n Perl scripting – good for string processing
n Lexical analyzers such as Lex or Flex
Page 3


1
Regular Expressions
2
Regular Expressions vs. Finite
Automata
n Offers a declarative way to express the pattern of any
string we want to accept
n E.g., 01*+ 10*
n Automata => more machine-like
< input: string  , output: [accept/reject]  >
n Regular expressions => more program syntax-like
n Unix environments heavily use regular expressions
n E.g., bash shell, grep, vi & other editors, sed
n Perl scripting – good for string processing
n Lexical analyzers such as Lex or Flex
3
Regular Expressions
Regular
expressions
Finite Automata
(DFA, NFA, e-NFA)
Regular
Languages
=
Automata/machines
Syntactical
expressions
Formal language
classes
Page 4


1
Regular Expressions
2
Regular Expressions vs. Finite
Automata
n Offers a declarative way to express the pattern of any
string we want to accept
n E.g., 01*+ 10*
n Automata => more machine-like
< input: string  , output: [accept/reject]  >
n Regular expressions => more program syntax-like
n Unix environments heavily use regular expressions
n E.g., bash shell, grep, vi & other editors, sed
n Perl scripting – good for string processing
n Lexical analyzers such as Lex or Flex
3
Regular Expressions
Regular
expressions
Finite Automata
(DFA, NFA, e-NFA)
Regular
Languages
=
Automata/machines
Syntactical
expressions
Formal language
classes
4
Language Operators
n Union of two languages:
n L U M = all strings that are either in L or M
n Note: A union of two languages produces a third
language
n Concatenation of two languages:
n L . M = all strings that are of the form xy
s.t., x Î L and y Î M
n The dot operator is usually omitted
n i.e., LM is same as L.M
Page 5


1
Regular Expressions
2
Regular Expressions vs. Finite
Automata
n Offers a declarative way to express the pattern of any
string we want to accept
n E.g., 01*+ 10*
n Automata => more machine-like
< input: string  , output: [accept/reject]  >
n Regular expressions => more program syntax-like
n Unix environments heavily use regular expressions
n E.g., bash shell, grep, vi & other editors, sed
n Perl scripting – good for string processing
n Lexical analyzers such as Lex or Flex
3
Regular Expressions
Regular
expressions
Finite Automata
(DFA, NFA, e-NFA)
Regular
Languages
=
Automata/machines
Syntactical
expressions
Formal language
classes
4
Language Operators
n Union of two languages:
n L U M = all strings that are either in L or M
n Note: A union of two languages produces a third
language
n Concatenation of two languages:
n L . M = all strings that are of the form xy
s.t., x Î L and y Î M
n The dot operator is usually omitted
n i.e., LM is same as L.M
5
Kleene Closure (the * operator)
n Kleene Closure of a given language L:
n L
0
= {e}
n L
1
= {w | for some w Î L}
n L
2
= { w
1
w
2
| w
1
Î L, w
2
Î L (duplicates allowed)}
n L
i
= { w
1
w
2
…w
i
| all w’s chosen are Î L (duplicates allowed)}
n (Note: the choice of each w
i
is independent)
n L* = U
i=0
L
i
(arbitrary number of concatenations)
Example:
n Let L = { 1, 00}
n L
0
= {e}
n L
1
= {1,00}
n L
2
= {11,100,001,0000}
n L
3
= {111,1100,1001,10000,000000,00001,00100,0011}
n L* = L
0
U L
1
U L
2
U …
“i” here refers to how many strings to concatenate from the parent
language L to produce strings in the language L
i