Formula Sheets: Regular Expressions, Languages, Grammar & Finite Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


Regular Expressions, Languages, Grammar & Finite A utomata
Regular Expressions
Regular Expression Op erations
• Union: R|S ={w|w?R or w?S} .
• C oncatenation: R·S ={rs|r?R,s?S} .
• Klee ne Star: R
*
=
?
8
i=0
R
i
, where R
0
={?} .
• Kle ene Plus: R
+
=
?
8
i=1
R
i
.
Iden tities
• ?R =R? =R .
• R|R =R .
• R|Ø =R , R·Ø =Ø .
• (R
*
)
*
=R
*
.
• R
*
=R
+
|? .
Arden’s Lemma
• Equation: R =Q+R·P , solution: R =QP
*
(if P do es not generate ? ).
Regular Languages
Language Definition
• Regular Language: L? S
*
accepted b y DF A, NF A, or de fined b y regular expression.
• Closure Prop erties:
– Union: L
1
?L
2
.
– In tersection: L
1
nL
2
.
– Complemen t: S
*
\L .
– Concatenation: L
1
·L
2
.
– Kleene Star: L
*
.
Pumping Lemma
• F or regular languageL ,?p (pumping length) suc h that forw?L ,|w|=p , w =xyz ,|xy|=p ,|y|> 0 ,
xy
i
z ?L for all i= 0 .
Finite A utomata
Deterministic Finite A utomata (DF A)
• Definition: M = (Q,S,d,q
0
,F) , where Q is states, S is alphab et, d : Q×S ? Q , q
0
is start state,
F ?Q is final states.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)?F} .
• Time Complexit y: O(|w|) .
Nondeterministic Finite A utomata (NF A)
• Definition: M = (Q,S,d,q
0
,F) , where d :Q×(S?{?})? 2
Q
.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)nF ?=Ø} .
• Time Complexit y: O(|w|·|Q|
2
) .
Epsilon-NF A
1
Page 2


Regular Expressions, Languages, Grammar & Finite A utomata
Regular Expressions
Regular Expression Op erations
• Union: R|S ={w|w?R or w?S} .
• C oncatenation: R·S ={rs|r?R,s?S} .
• Klee ne Star: R
*
=
?
8
i=0
R
i
, where R
0
={?} .
• Kle ene Plus: R
+
=
?
8
i=1
R
i
.
Iden tities
• ?R =R? =R .
• R|R =R .
• R|Ø =R , R·Ø =Ø .
• (R
*
)
*
=R
*
.
• R
*
=R
+
|? .
Arden’s Lemma
• Equation: R =Q+R·P , solution: R =QP
*
(if P do es not generate ? ).
Regular Languages
Language Definition
• Regular Language: L? S
*
accepted b y DF A, NF A, or de fined b y regular expression.
• Closure Prop erties:
– Union: L
1
?L
2
.
– In tersection: L
1
nL
2
.
– Complemen t: S
*
\L .
– Concatenation: L
1
·L
2
.
– Kleene Star: L
*
.
Pumping Lemma
• F or regular languageL ,?p (pumping length) suc h that forw?L ,|w|=p , w =xyz ,|xy|=p ,|y|> 0 ,
xy
i
z ?L for all i= 0 .
Finite A utomata
Deterministic Finite A utomata (DF A)
• Definition: M = (Q,S,d,q
0
,F) , where Q is states, S is alphab et, d : Q×S ? Q , q
0
is start state,
F ?Q is final states.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)?F} .
• Time Complexit y: O(|w|) .
Nondeterministic Finite A utomata (NF A)
• Definition: M = (Q,S,d,q
0
,F) , where d :Q×(S?{?})? 2
Q
.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)nF ?=Ø} .
• Time Complexit y: O(|w|·|Q|
2
) .
Epsilon-NF A
1
• ? -Closure: Set of states reac hable from q via ? -transitions.
• Con v ersion to DF A: d
D
(S,a) =? -closure(
?
q?S
d
N
(q,a)) .
DF A Minimization
• P artition states in to equiv alen t classes: Distinguishable if one leads to accept, other to reject.
• Time Complexit y: O(|Q|log|Q|) .
A utomata with Output
Mo ore Mac hine
• Definition: M = (Q,S,?,d,?,q
0
) , where ? is output alphab et, ? :Q? ? is output function.
• Output: Dep ends on curren t state, ?(q) .
• Time Complexit y: O(|w|) .
Mealy Mac hine
• De finition: M = (Q,S,?,d,?,q
0
) , where ? :Q×S? ? .
• Output: Dep e nds on state and input, ?(q,a) .
• Time C omplexit y: O(|w|) .
Con v ersions
NF A to DF A ( Subset Construction)
• DF A state: Subset o f NF A states.
• T ransition: d
D
(S,a) =
?
q?S
d
N
(q,a) .
• Time C omplexit y: O(2
|Q|
) .
Regular Expre ssion to NF A (Thompson’s Construction)
• Constructs N F A with ? -transitions for R .
• Time C omplexit y: O(|R|) .
DF A to R egular Expression
• State Elimination: C om bine transitions as regular expressions.
• Time C omplexit y: O(|Q|
3
) .
Op erations on DF A
Union
• F or DF As M
1
= (Q
1
,S,d
1
,q
01
,F
1
) , M
2
= (Q
2
,S,d
2
,q
02
,F
2
) :
• Pro duct A utomaton: M = (Q
1
×Q
2
,S,d,(q
01
,q
02
),F
1
×Q
2
?Q
1
×F
2
) .
In tersection
• Pro duct A utomaton: M = (Q
1
×Q
2
,S,d,(q
01
,q
02
),F
1
×F
2
) .
Complemen t
• F or DF A M = (Q,S,d,q
0
,F) , complemen t: M
'
= (Q,S,d,q
0
,Q\F) .
2
Page 3


Regular Expressions, Languages, Grammar & Finite A utomata
Regular Expressions
Regular Expression Op erations
• Union: R|S ={w|w?R or w?S} .
• C oncatenation: R·S ={rs|r?R,s?S} .
• Klee ne Star: R
*
=
?
8
i=0
R
i
, where R
0
={?} .
• Kle ene Plus: R
+
=
?
8
i=1
R
i
.
Iden tities
• ?R =R? =R .
• R|R =R .
• R|Ø =R , R·Ø =Ø .
• (R
*
)
*
=R
*
.
• R
*
=R
+
|? .
Arden’s Lemma
• Equation: R =Q+R·P , solution: R =QP
*
(if P do es not generate ? ).
Regular Languages
Language Definition
• Regular Language: L? S
*
accepted b y DF A, NF A, or de fined b y regular expression.
• Closure Prop erties:
– Union: L
1
?L
2
.
– In tersection: L
1
nL
2
.
– Complemen t: S
*
\L .
– Concatenation: L
1
·L
2
.
– Kleene Star: L
*
.
Pumping Lemma
• F or regular languageL ,?p (pumping length) suc h that forw?L ,|w|=p , w =xyz ,|xy|=p ,|y|> 0 ,
xy
i
z ?L for all i= 0 .
Finite A utomata
Deterministic Finite A utomata (DF A)
• Definition: M = (Q,S,d,q
0
,F) , where Q is states, S is alphab et, d : Q×S ? Q , q
0
is start state,
F ?Q is final states.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)?F} .
• Time Complexit y: O(|w|) .
Nondeterministic Finite A utomata (NF A)
• Definition: M = (Q,S,d,q
0
,F) , where d :Q×(S?{?})? 2
Q
.
• Language: L(M) ={w? S
*
|d
*
(q
0
,w)nF ?=Ø} .
• Time Complexit y: O(|w|·|Q|
2
) .
Epsilon-NF A
1
• ? -Closure: Set of states reac hable from q via ? -transitions.
• Con v ersion to DF A: d
D
(S,a) =? -closure(
?
q?S
d
N
(q,a)) .
DF A Minimization
• P artition states in to equiv alen t classes: Distinguishable if one leads to accept, other to reject.
• Time Complexit y: O(|Q|log|Q|) .
A utomata with Output
Mo ore Mac hine
• Definition: M = (Q,S,?,d,?,q
0
) , where ? is output alphab et, ? :Q? ? is output function.
• Output: Dep ends on curren t state, ?(q) .
• Time Complexit y: O(|w|) .
Mealy Mac hine
• De finition: M = (Q,S,?,d,?,q
0
) , where ? :Q×S? ? .
• Output: Dep e nds on state and input, ?(q,a) .
• Time C omplexit y: O(|w|) .
Con v ersions
NF A to DF A ( Subset Construction)
• DF A state: Subset o f NF A states.
• T ransition: d
D
(S,a) =
?
q?S
d
N
(q,a) .
• Time C omplexit y: O(2
|Q|
) .
Regular Expre ssion to NF A (Thompson’s Construction)
• Constructs N F A with ? -transitions for R .
• Time C omplexit y: O(|R|) .
DF A to R egular Expression
• State Elimination: C om bine transitions as regular expressions.
• Time C omplexit y: O(|Q|
3
) .
Op erations on DF A
Union
• F or DF As M
1
= (Q
1
,S,d
1
,q
01
,F
1
) , M
2
= (Q
2
,S,d
2
,q
02
,F
2
) :
• Pro duct A utomaton: M = (Q
1
×Q
2
,S,d,(q
01
,q
02
),F
1
×Q
2
?Q
1
×F
2
) .
In tersection
• Pro duct A utomaton: M = (Q
1
×Q
2
,S,d,(q
01
,q
02
),F
1
×F
2
) .
Complemen t
• F or DF A M = (Q,S,d,q
0
,F) , complemen t: M
'
= (Q,S,d,q
0
,Q\F) .
2
Regular Grammar
Righ t-Linear Grammar
• Pro d uctions: A?a or A?aB , where A,B are v ariables, a is terminal.
• Generates regular languages.
Left-Linear Grammar
• Pro d uctions: A?a or A?Ba .
• Equiv a len t to regular languages.
3