Formula Sheets: Introduction to Grammars, Languages & Automata | Theory of Computation - Computer Science Engineering (CSE) PDF Download

 Page 1


In tro duction to Grammars, Languages & A utomata
Languages and Grammars
Language Definition
• Language: L? S
*
, where S is a finite a lphab et, S
*
is all p ossible strings.
• Empt y String: ? , string of length 0.
Grammar Definition
• Grammar: G = (V,T,P,S) , where V is v ariables, T is terminals, P is pro ductions, S is start sym b ol.
• Pro duction: a?ß , where a? (V ?T)
+
, ß ? (V ?T)
*
.
Chomsky Hierarc h y
• T yp e 0 (Unrestricted): No restrictions on a?ß .
• T yp e 1 (Con text-Sensitiv e): a?ß where |a|=|ß| , or a?? allo w ed.
• T yp e 2 (Con text-F ree): A?ß , where A?V , ß ? (V ?T)
*
.
• T yp e 3 (Regular): A?a or A?aB , where A,B ?V , a?T .
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} , where d
*
is extended transition function.
• Time Complexit y: O(|w|) , where |w| is input string length.
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
) for sim ulation.
Pushdo wn A utomata
Pushdo wn A utomata (PD A)
• Definition: M = (Q,S,G,d,q
0
,Z
0
,F) , where G is stac k alphab et, d :Q×(S?{?})×G? 2
Q×G
*
, Z
0
is initial stac k sym b ol.
• Language: C on text-free languages, L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?),q ?F} .
T uring Mac hines
T uring Mac hine (TM)
• Definition: M = (Q,S,G,d,q
0
,q
accept
,q
reject
) , where G is tap e alphab et,d :Q×G?Q×G×{L,R,S} .
• Language: Re cursiv ely en umerable, L(M) ={w? S
*
|q
0
w?
*
q
accept
} .
Recursiv e F unction Theory
Computable F unctions
• F unction f :N
k
?N is computable if there exists a T uring Mac hine that computes f .
Recursiv e vs Recursiv ely En umerable
• Recurs iv e: TM halts on all inputs (decidable).
1
Page 2


In tro duction to Grammars, Languages & A utomata
Languages and Grammars
Language Definition
• Language: L? S
*
, where S is a finite a lphab et, S
*
is all p ossible strings.
• Empt y String: ? , string of length 0.
Grammar Definition
• Grammar: G = (V,T,P,S) , where V is v ariables, T is terminals, P is pro ductions, S is start sym b ol.
• Pro duction: a?ß , where a? (V ?T)
+
, ß ? (V ?T)
*
.
Chomsky Hierarc h y
• T yp e 0 (Unrestricted): No restrictions on a?ß .
• T yp e 1 (Con text-Sensitiv e): a?ß where |a|=|ß| , or a?? allo w ed.
• T yp e 2 (Con text-F ree): A?ß , where A?V , ß ? (V ?T)
*
.
• T yp e 3 (Regular): A?a or A?aB , where A,B ?V , a?T .
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} , where d
*
is extended transition function.
• Time Complexit y: O(|w|) , where |w| is input string length.
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
) for sim ulation.
Pushdo wn A utomata
Pushdo wn A utomata (PD A)
• Definition: M = (Q,S,G,d,q
0
,Z
0
,F) , where G is stac k alphab et, d :Q×(S?{?})×G? 2
Q×G
*
, Z
0
is initial stac k sym b ol.
• Language: C on text-free languages, L(M) ={w? S
*
| (q
0
,w,Z
0
)?
*
(q,?,?),q ?F} .
T uring Mac hines
T uring Mac hine (TM)
• Definition: M = (Q,S,G,d,q
0
,q
accept
,q
reject
) , where G is tap e alphab et,d :Q×G?Q×G×{L,R,S} .
• Language: Re cursiv ely en umerable, L(M) ={w? S
*
|q
0
w?
*
q
accept
} .
Recursiv e F unction Theory
Computable F unctions
• F unction f :N
k
?N is computable if there exists a T uring Mac hine that computes f .
Recursiv e vs Recursiv ely En umerable
• Recurs iv e: TM halts on all inputs (decidable).
1
• Recursiv ely En umerable: TM halts on accepting inputs (semi-decidable).
Language Classes and A utomata
Language-A utomata Mapping
• Regular Languages: DF A, NF A, Regular Expressions (T yp e 3).
• Con text-F ree Languages: PD A, Con text-F ree Grammar (T yp e 2).
• Con text-Sensitiv e Languages: Linear Bounded A utomata (T yp e 1).
• Recursiv ely En umerable Languages: T uring Mac hine (T yp e 0).
Pro ving T ec hniques
Pumping Lemma for Regular Languages
• F or regular languageL ,?p (pumping length) suc h that forw?L ,|w|=p ,w =xyz ,|xy|=p ,|y|> 0 ,
and xy
i
z ?L for all i= 0 .
Pumping Lemma for Con text-F ree Languages
• F or con text-free language L , ?p suc h that for w ? L , |w| = p , w = uvwxy , |vwx| = p , |vx| > 0 , and
uv
i
wx
i
y ?L for all i= 0 .
2