Transcript Regular Expressions

Recap: Transformation NFA  DFA
e
e
s1 e
s2



pi
...
>s
si
p1
p2
>
s
s1
...
sn

p1
p2
...
pm
Closure Under Set Operations
Theorem. Let L and M two regular languages, then the
following languages are also regular:
•LM
• LC
•LM
•L–M
• LM
• L*
Regular Expressions
A regular expression is defined inductively over the
alphabet   { (, ), e, , , *} as follows:
•, e, and each character in  are regular expressions (step 0)
•If  and  are regular expressions then:
• (  )
• ()
• *
are also regular expressions (inductive step)
•No other string over the alphabet   { (, ), e, , , *} is
a regular expression
 Exceptions: , *, +, k (for a fixed k > 0)
Language Representing Regular
Expressions
We define a mapping from a regular expression  to a language
L() as follows:
•Step 0:
•L() = {}
•L(e) = {e}
•L() ={} for each   
•Inductive step:
•L((  )) = L()  L()
•L(()) = L()L()
•L(*) = L()*
Example (1)
Example 1. Find L((ab*)a)
L(ab*a) = L(a)L(b)*L(a)
= {w : w is of the form abna with n = 0, 1, 2,…}
Example 2. Find L((a(a b)*)).
L(a(a b)*) = L(a)(L(a)  L(b))*
= {aw : w is a word in }
Example (2)
Find the regular expression for the language L in the alphabet
{a,b} such that the words in L contains the substring aaa
Find the regular expression for the language L in the alphabet
{a,b} such that the words in L contains the substring aaa or
bbb
Main Theorem About Finite Automata
(Kleene)
(1) Given a finite automata A, there is a regular expression expr
such that L(A) = L(expr)
(2) Given a regular expression expr, there is a finite automata A
such that L(A) = L(expr)
Regular languages
regular expressions
Theorem 1.54
Input: a regular expression expr
Output: a finite automaton accepting L(expr)
1. Convert any step-0 element (any of the characters in ,
 or e) occurring in expr to a finite automaton accepting
this element
2. Apply the theorem about closure under set operations to
every
•
•
•
Union
Concatenation
Kleene star
Example
Obtain a finite automaton accepting the regular expression:
((a ab)*ba)*.
The impact of this Algorithm is a dream (or a nightmare?)
of programmers: given the specification of a language there
is an algorithm that recognizes it automatically.
Example: Yak and Lex tools in Unix.
Lemma 1.60
Input: a finite automaton A
Output: a regular expression expr such that L(expr) = L(A)
Assumptions about the automaton A:
•A has a single favorable state
•There are no transitions directed to the initial state
• There are no transitions starting at the favorable state
•Nodes will be labeled 1, 2, …, n, where 1 is the initial
state and n is the favorable state
Definition. An generalized NFA is am NFA in which the
arrows are labeled by regular expressions. (Unlike regular
NFAs in which transitions are only labeled by characters in
)
Construction (1)
for every pair of nodes such that there is more than one transition
from one to the other one:
expr1
expr2
…
exprn
expr1  expr2  …  exprn
Construction (2)
for every pair of nodes such that there is an intermediate node
connecting them:
expr3
expr1
expr2
expr1 (expr2)* expr3
Example
a
a
>s
b
b
q
b
r
b
Homework Friday Sep. 21
•
•
•
•
1.12
1.21 (a)
1.28 (c)
1.43 (either picture and an accompanying
explanation or formal proof are fine)
• 1.60 (either state diagram or formal
definition are fine)