Post on 31-Oct-2015
description
transcript
Limbaje Formale si Automate
Instructor Andrei PAUN
Semestrul II 2009-2010
Departmentul de InfomrmaticaUniversitatea BucurestiBucuresti, Romania
1
apaunRectangle
Structura cursului:
1. Cunostinte de bazamultimi, multiseturi, secvente, functii,relatii, metode si tehnici de demonstratie,alfabet, cuvinte, limbaje
2. Automate niteautomate nite nedeterministe (NFA),automate nite deterministe (DFA),transformarea de la NFA la DFA,proprietati pentru limbajele acceptate de
automate,lema de pompare
3. Expresii regulateechivalenta dintre expresiile regulate si au-
tomatele nite(in denirea limbajelor)
4. Gramatici independente de context (CFG)simplicare si forme normale,algoritmi de parsare, lema de pompare sialte proprietati
2
5. Automate pushdown (PDA)nondeterministic pushdown automata (NPDA),deterministic pushdown automata (DPDA),PDA vs. CFGs
6. Masini Turing (TM)diverse tipuri de TM, TM universale,decidabilitate si nedecidabilitate,complexitate de timp si spatiu
3
Motivare pentru curs
Compiler
Programming
Database
AI
Graphics
VLSI
Theory of Computing
(1) Putere de calcul
(2) Complexitate
(3) Software design
(4) Circuit design
. . . . . . . . . . . . . . . . . . . . .
4
I. Cunostinte de baza
1. Multimi1) O multime este o colectie de elemente luatedintr-un univers.
2) O multime este nita daca contine un nu-mar nit de elemente, si este innita in cazcontrar.
3) Cardinalitatea unei multimi este numarul saude elemente si se noteaza cu # sau (pen-tru multimea ).
5
Cum specicam o multime:
(1) Listam toate elementele sale:{} (or ), = {2, 3, 5, 7}, = {3, 2, 2, 7, 5, 7}
(2) Precizam o proprietate: { ()} = { este numar prim}, = { este un cuvant in romana si
este si palindrom}, = { este un intreg divizibil cu
3 si mai mic decat 10 }
(3) Denite recursiv:Forma generala:i) Anumite elemente initiale sau de baza
sunt in ii) Daca , , atunci iii) Nici un alt element nu apartine lui
6
Exemplu Denirea lui A:i) 2 ii) Daca , , atunci + iii) Nici un alt element nu apartine lui
(4) Inchiderea la operatii
Spunem ca o multime este inchisa la o op-eratie binara daca pentru toate , ,
Fie si este inchisa la . Spunem ca este o inchidere a lui la operatia dacanu exista astfel incat si esteinchisa la .
Forma generala (pentru multimi denite prininchidere) este cea mai mica multime care contine an-umite elemente initiale (de baza) si care esteinchisa la operatia .
7
Exemplu este cea mai mica multime care il continepe si este inchisa la +.
Operatii cu multimiDaca se dau si doua multimi:
= { este in sau este in }
= { este in si este si in }
= { este in si nu este in }
8
=1 = { este in , pentru un , 1 }=1 = { este in , 1 }
Proprietati ale operatiilor cu multimi
Distributivitate ( ) = ( ) ( ) ( ) = ( ) ( )Indempotenta = ; = Involutie() = Comutativitate = ; = Asociativitate ( ) = ( ) ( ) = ( )
9
Regulile lui De Morgan( ) = ( ) =
Multimea submultimilorMultimea tuturor submultimilor unei mul-timi (power set of ) se noteaza cu 2.
Exemplu: = {2, 3, 5}2 = {, {2}, {3}, {5}, {2, 3}, {2, 5}, {3, 5}, {2, 3, 5}}
Cateva multimi speciale:: multimea vida;: multimea intregilor; : multimea intregilor pozitivi;0: multimea intregilor care nu sunt negativi;: multimea numerelor reale.. . . . . . . . . . . . . . .
10
2. MultiseturiUn multiset este o colectie de elementedintr-un univers oarecare, colectie in carerepetitiile nu sunt ignorate.
3. SecventeO secventa de elemente dintr-un univers oare-care este o lista de elemente care suntordonate (ecare element are o pozitie).
11
4. Functii
Denitie Daca se dau doua multimi si , ofunctie (partiala) de la la asociaza cuecare din (cel mult) un element din .
Notatii:functie : asocierea () = nedenita () =
Functii speciale:
functia identitate: : si () = pentru toti Functia caracteristica a lui pentru : : {, } () = , () = ,
12
Cateva proprietati ale functiilor : totala: () este denita pentru toate elementele
din surjectiva:pentru toate elementele din exista un
din astfel incat () = injectiva:, , = implica faptul ca () = ()
bijectiva:in acelasi timp si surjectiva si injectiva
Notatia big-O
() = (()) daca exista > 0 si intregul poz-itiv astfel incat pentru toate
() () () = (()) daca
() () () = (()) daca
() = (()) si () = (())
13
functie (partiala) ,
: 1 2 . . . 1 . . . (1, 2, . . . , ) = (1, . . . , )
sau (1, 2, . . . , ) =
14
5. Relatii
O relatie -ara , 1, pentru multimile1, . . . , este orice submultime a produsu-lui cartezian 1 . . . .Exemplu
= {1, 2}, = {1, 2, 3, 4} = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 4)}
15
Compunerea relatiilor
Fie si doua relatii. Atuncicompunerea lui cu , notata prin , esterelatia , denita prin: = {(, ) (, ) este in si (, ) este in
pentru un din }
Compunerea unei relatii : cu ea insasi0 : {(, ) este in }1 : , 1 : 1+ = =1 inchiderea tranzitiva a lui = =0 inchiderea reexiva si tranzitiva alui
16
Proprietatile relatiei reexiva: pentru toti din
simetrica: implica
antisimetrica: , implica =
17
tranzitiva: , implica
O relatie binara peste este orelatie de echivalenta daca este
reexiva, simetrica, si tranzitiva.
O relatie de echivalenta peste deneste submultimi disjuncte ale lui ,numite clase de echivalenta.
[] = { este in si }
18
Fie o relatie binara de echivalenta peste si .Spunem ca este -inchisa daca pentru toti din , implica faptul ca este in .
Exemplu : multimea intregilor; = {9, 4, 3, 2}; :este patratul lui (is the square
of)Atunci este -inchisa.
este o relatie n-ara peste . este-inchisa daca pentru toate 1, . . . , 1 din ,avem ca daca (1, . . . , 1, ) este in atunci este in .
Exemplu : multimea tuturor intregilor; = {(, , ) = }; = { 1} pentru un intreg
Atunci este -inchisa.
19
Lema Fie o relatie de echivalenta peste .Atunci pentru toti , din avem sau [] =[] sau [] [] =
O relatie binara peste este o ordine par-tiala daca este reexiva, tranzitiva, si antisimetrica.
Inchidere + este inchiderea tranzitiva a lui
O reprezentare in digraf pentru o inchideretranzitiva:
20
6. Cardinalitate
Daca se dau doua multimi si , spunemca ele au cardinalitate egala daca exista obijectie : .Exemplu # = #0 () = 2 1, < 0 () = 2, 0
O multime este numarabila sau enumerabiladaca este ori nita ori innita, caz in care areaceeasi cardinalitate cu .
21
7. Metode de demonstratie
demonstratie directa
demonstratie prin contradictie
demonstratie prin inductie
Demonstratie directaEnumeram toate cazurile pentru a arata ca
proprietatea este adevarate.
Exemplu Orice numar par dintre 4 si 232 estesuma a doua numere prime.
Demonstratie prin contradictieStabilim validitatea propozitiei presupunand
ca nu este adevarata si inferam o contradictie.
Exemplu Exista un numar innit de numereimpare.
22
Demonstratia prin inductie baza
ipoteza inductiva
pasul inductiv
concluzie
Two forms:(1) Prove it holds for a basis value ,
Hypothesize it holds for value , Prove it holds for value + 1.
(2) Prove it holds for basis values, Hypothesize it holds for all values
less than and greater than basisvalue,
Prove it holds for value .
23
Example (proof by induction)
(i) no two lines are parallel;
(ii) no three lines have a common intersec-tion point.
Prove that the number of regions in anarrangement of lines is
1 + ( + 1)/2
24
8. Proof Techniques
pigeonhole principle
counting
diagonalisation
The Pigeonhole PrincipleLet 1 be an integer, let there be pigeonholes, and there be + 1 items of mailto be placed in the pigeonholes. Then, how-ever the the items are placed, at least onepigeonhole will contain at least two items.
The Pigeonhole Principle(Extended version)Let 1, . . . , 1. There exists a positive inte-ger (1, . . . , ). If (1, . . . , ), then how-ever items are placed into pigeonholes,there exists , 1 such that the -thpigeonhole contains at least 1 + 1 items.
25
Example Let = (,) be a digraph with# = 1. Then has a cycle if and only if has a path of length at least .
6
R
:
k
26
9. Alphabets, Words, and Languages
An alphabet is a nite, nonempty set ofelements.The elements of the alphabet are calledsymbols or letters.
A word over an alphabet is a nite se-quence of symbols from .
A language is a set of words.Examples:(1) English alphabet, words and language.
(2) Alphabet: {, }words: , , , , , . . . . . .language: {, , , , . . . . . .}
i.e. { 0}(3) Alphabet : Fortran reserved words and
identierswords : a Fortran programLanguage : the set of all Fortran
programs.
27
Empty word is a word over every alphabet.
The length of a word is the number of sym-bols in the given word.
Example: = 0 = 4
The -length of a word is the number oftimes occurs in .
Example: 011010 = 2 = 0
28
The catenation of two words and , de-noted by , is the word obtained by append-ing the word to .
Example = = = =
= =
=
Catenation is associative:() = ()
= + 0 = (Power of a word)
= 1, 1Example ()0 =
()3 =
29
Prex: is a prex of if such that =
Example is a prex of is a prex of any word Any word is a prex of itself
Sux: is a sux of if such that =
Example is a sux of is a sux of any word 01011 is a sux of 01011
Subword: is a subword of if , s.t. =
Example The subwords of are:
, , , , , , , , , ,
Proper prex (sux, subword): is a proper prex (sux, subword) of if is a prex (sux, subword) of and = and = .
30
Reversal:(i) = , if = ;(ii) = , if = for , is a word
Lemma If = 1 . . . for some 0, then = . . . 1.
Proof: By induction on .Basis: = 0. = by (i).I.H.: Assume Lemma holds for all
with = .I.S.: Consider a word with = + 1.
Then = 1 . . . +1 = 1, where
= 2 . . . +1.
Then = 1.But = , by I.H., = +1 . . . 2,so we get
= +1 . . . 1.
Universal Language over : = {0, 1}, = {, 0, 1, 00, 01, 10, 11, 000, . . .}
31
Mappings (Morphism and Substitution)
Denition Let and be two alphabets.Then a mapping : is said to bea morphism if(i) () = ;(ii) () = ()(), for all , in .
Note: (ii) implies that we need only denethe images of letters to dene the images ofwords.
Example: = {0, 1}, = {, , , },(0) = , (1) = .Then (1001) = (1)(0)(0)(1) = =
A morphism is said to be -free if, for all = , () = .
32
Denition Let and be two alphabets. Amapping : 2 is said to be asubstitution ifi) () = {};ii) () = ()(), for all , .
Example:1 = {, }, 1 = {, , },a substitution 1:1() = {, , };1() = {, }.
Then 1() =
Example:2 = {0, 1, 2}, 2 = {, },2(0) = { 1}2(1) = { 1}2(2) = {}
Then 2(1020) =
33
Given an alphabet , is dened as fol-lows:(i) ;(ii) if , then for all .
A language over an alphabet is a subsetof , i.e., .
Example: is a language over every alphabet .{} is a language over every alphabet.{ 0} is a language over {, }{ 0} is a language over {, , }
34
Catenation of Languages1 2 = {1 2 1 in 1, 2 in 2},usually written as 12.
Examples
1 = {, }; 2 = {, }12 = {, , }
(Note that 12 = {(, ), (, ), (, ), (, )})
1 =
{}1 ={} = = {, }; = {, } =
35
Powers of Languages:0 = {}+1 = , 1
Plus+ = =1
Star = =0 0 1 2 . . . . . .
Examples = {, }. Then
0 = {}1 = = {, }2 = {, , , }0 = {} = {}0 = {}
= {, , , , , , , . . . . . .}(Note 4)
36
Reversal of Languages = { is in }
Examples = {, , }; = {, , }
= { > > 0} = { > > 0}
properties of reversal
( ) = ( ) =
() =
(+) = ()+
() = ()
Complementation of LanguagesGiven a language over , =
= ? {} () = = { 0} over = {, } =
37
Alternative denition of + and
+ = { in = 12 . . . , for1, 2, . . . , and 1}
= { in = 12 . . . , for1, 2, . . . , and 0}
Given a word in , and a language to test if is in we use = =0 and testif is in 0, 1, . . . .
38
Property Summaries properties of catenation (of languages)
Associativity 1(23) = (12)3Identity {} = {} =
Zero = =
Distributivity 1(2 3) = 12 13w.r. (1 2)3 = 13 23
Distributivity does not hold with respect to properties of Plus and Star
= + {} ( But + = {}?)+ =
(+)+ = +, () =
+ = , = {}, 0 = {}{}+ = {}, {} = {}, 2 = + = +, =
+ + and
39
Chapter 2. FINITE AUTOMATA
Example Design a sequential lock. Thelock has 1-bit sequential input. Initially thelock is closed. If the lock is closed it will openwhen the last three input signals are 1, 0,1, and then remains open.
state (transition) diagram
state (or transition) table
40
state set : {0, 1, 2, 3}input alphabet : {0, 1}Transition function : (0, 0) = 0, (0, 1) = 1, . . .Start state : 0Final state set : {3}
Deterministic Finite Automata (DFA) = (, , , , ) where
is a nite nonempty set of states is the input alphabet : transition functions start state nal state set
41
A computer is a nite state system (i.e. FA)which has millions of states.
There are many examples of FINITESTATE SYSTEMS. A nite automaton is anABSTRACTION of them.
View a DFA as a machine
42
Specifying 1)
State diagram(Transition diagram)
Start state
Final state
2)
43
Congurationsa word in
where is the present state, and is the remaining input
Example:
0 . . . 1 . . . 2(start conguration) (nal conguration)
Moves of a DFA0 1 1 2 if = and (, ) =
Conguration sequence0 1 2
+ and is a binary relation over .+ : transitive closure of . : reexive transitive closure of .
44
0 + 20 20 00 2 2
if 11 22 . . .
steps
Accepting Conguration Sequence0 1 2
can also be viewed as a function : ,
since the next conguration is determineduniquely for a given conguration.
The DFA stops when:(i) we have no more input,or (ii) the next conguration is undened.
45
A word is said to be accepted by a DFA if , .The language of a DFA , (), is denedas:
() = { , for some }Examples
() =
() =
46
DFA membership problem
DFA MEMBERSHIP
INSTANCE: A DFA, = (,, , , )and a word .
QUESTION: Is in () ?
Run the DFA with input .In at most steps it accepts, rejects oraborts.
Examples
Checking for words thatcontain as subword.
Check:
47
Let denote any letter of English alphabetand any decimal digit; the form ofPASCAL IDENTIFIERS can be speciedby
Recognizing comments that may go overseveral lines.
/*................*/
: symbols other than and /48
A DFA which has a total is saidto be complete; if is nontotal it isincomplete.
Theorem. Every incomplete DFA can be completed by adding onenew state (sink) to give DFA such that ( ) = ().
Example:
() is the set of all words thatdo not contain two consecutive s.
49
Two DFA 1 and 2 are equivalentif (1) = (2).
The collection of languages acceptedby DFAs is denoted by
.
It is called the family of DFA languagesand it is dened as:
= { = () for some DFA }
= { 1} is not acceptedby any DFA.
50
Proof: Use contradiction andPigeonhole principle.
Assume = (), for some DFA
= (, {, }, , , ).Let = #. Consider the acceptingconguration sequence for ,
0 11 . . . . . . 2
where 0 = and 2 . Now + 1 statesappear during the reading of , butthere are only distinct states in .By Pigeonhole principle at least onestate must appear at least twice duringthe reading of s.
Assume = , 0 < .Then
0() . . .
. . . . . . 2
Therefore () .This is a contradiction.
51
= {}, 1.For any 1, is a DFA language?
= { : 0 }, 1.For any 1, is a DFA language ?
52
Nondeterministic Finite Automata (NFA)
= (,, , , )same as a DFA except . is a nite transition relation.
In a DFA is a transition function: : It can be viewed as a relation : In a NFA, can be be viewed as a function: : 2
Examples:NFA for words in {, } that contain threeconsecutive as.
53
Both (0, , 1) and (0, , 3) are in .
We dene acceptance by existenceof a computation that leads to a nalstate.
Conversely, we dene rejection bythe nonexistence of any computationthat leads to a nal state.
The language of an NFA = (,, , , )is dened by
() = { , for some in }.
54
The family of NFA languages is dened by:
= { = (), for some NFA }.
Two NFAs 1, and 2 are equivalent if(1) = (2).
Why NFA?
(i) easy to construct;(ii) useful theoretically;(iii) are of same power as DFA.
Note:
congurations are dened in the same wayTransition (move)
if = , for some , and (, , ) .
55
Transforming NFA to DFA
Consider the NFA 1 again
There are only limited number of choices.For example:
0 1 1 20 3 3{0} {1, 3} {1, 3} {2}Why limited number of choices?
The state set is nite.
We summarize the choices at each stepby combining all conguration sequencesinto one super-conf. sequence.
{0} {1, 3} {1, 3} {2}.56
We now have a set of all possiblestates at each step. From this pointof view the computation of the NFAon an input word is deterministic.
A super-conguration has the form
where and .Note that is a super-conf.,it means that the NFA cannot bein any state at that point, i.e.,an abort has occured.
We say that
if = , for some , and = { (, , ) , for some }
57
More examples on super-congurations
: () is the set of all wordsthat have as a subword.
The super-conguration sequenceon input word is as follows:
{0} {0} {0, 1} {0, 1} {0, 2} {0, 2}
58
Notice that given a set andan input symbol , the set s.t. is uniquely determined.
Lemma (2.3.1) (Determinism Lemma)Let = (,, , , ) be an NFA.Then for all words in and forall . and implies
= .
Lemma (2.3.2) Let = (,, , , )be an NFA. Then for all words in
and for all in ,
i {} , for some with in .
59
Example (Transformation of an NFA to a DFA)
= (,, , , ) where
= 0, 1, 2, = , = 0, = {2}
= (,, , , ) where
= 2 = {, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}
(, ) = { (, , ) and }60
= {0} = {
Algorithm NFA to DFAThe Subset Construction
On entry: An NFA = (,, , , ).
On exit: A DFA = (,, , , )satisfying () = ( ).
begin Let = 2, = {} and = { , and = }We dene : byFor all and for all ,(, ) = , if in .
end of Algorithm
if = { (, , ) and }61
= {0}
Algorithm NFA to DFA 2The Iterative Subset Construction
62
Theorem Given an NFA = (,, , , ), thenthe DFA = (,, , , ) obtained by ei-ther subset construction satises( ) = ().
Proof:By Lemma 2.3.2, for all in , i {} for some with
By the construction of ,{} in i{} in .
() , for some {} , , in {} , in and = , ( )
63
TheoremEvery NFA Language is a DFA language andconversely.( = )
ExampleEvery nite language is accepted by a DFA.
64
NFA
It is useful to loosen the denition of NFAeven more by allowing the read head to re-main over the same symbol of the input andread nothing.
Example1 = { 0, 0}M:
() = 1
: (0, , 0)
(0, , 1) (1, , 1)
0 0 0 1 10 1 1 10 0 1
65
Formally, a -NFA = (,, , , )where , , , are as before, but is a nite transition relationfor which
( {})
Congurations are as before. is dened by
if either = for and (, , ) or = and (, , )
ExampleGiven FA 1 and 2, constructa FA 3 such that(3) = (1) (2)
66
Transforming -NFA to NFA
Two steps:Step I: completionStep II: transition removal(I). -Completion
Given a -NFA = (,, , , )perform the following process:
For all , , :whenever (, , ), (, , ) are in add (, , ) to
until no new transitions are added to and let this be .
Let the new NFA be = (,, , , )where = { (, , ) and }and = {(, , ) + }
Example:
67
Claim 1: For any , , + if and only if
Claim 2: For any , , , if and only if
Theorem: ( ) = ()
Example:
68
(II) Transition Removal
Given a -completed -NFA
= (, , , , ),
perform the following process:
(0) = ;() For all , , ,
if (, , ) and (, , ) in
then add (, , ) to ;() Delete all -transitions from .
Now we got = (, , , , )where = ( {(, , ) (, , ), (, , ) }){(, , ) , }Example
69
Claim Whenever
for some , we have
and vice versa.
Claim ( ) = ()
Theorem =
70
Properties of FA Languages
I. Closure Properties
Union: The union of two DFA languagesis a DFA language.Proof: Given 1 = (1) and 2 = (2),1, 2 are generic DFA languages.
1 = (1, 1, 1, 1, 1) and
2 = (2, 2, 2, 2, 2).
Construct a -NFA = (, , , , ) where
= 1 2 {} = 1 2 = 1 2 {(, , 1), (, , 2)} = 1 2
71
Now we claim that () = 1 2
(1) Let be a generic word in (). () implies + for some 1 or 2.
If 1, then 1 and then1 1 . We know that (1).
If 2, then 2 . Since2 2 , we know that (2),
therefore (1) (2), i.e., 1 2.So () 1 2.
(2) Let be a generic word in 1 2.Without losing of generality we can assumethat 1, i.e., (1).Then 1 1 , for some 1.Then 1 . Therefore ().So, 1 2 ().
(3) By the results of (1) and (2), we conclude() = 1 2.
Since every -NFA language is a DFA language,() is a DFA language.
72
2. Complementation:
The complement of a DFA language is a DFA language.Proof: There is a complete DFA = (, , , , ) with = (). Dene = (, , , , )
3. Intersection:
1 and 2
= 1 2 = 1 2
73
4. Catenation:
The catenation of two DFA languages is aDFA language:
1 = (1, 1, 1, 1, 1);2 = (2, 2, 2, 2, 2).
() = (1)(2)
= (1 2, 1 2, , 1, 2), = 1 2 {(, , 2) 1}
= (, , , , ) where
= 1 2 = 1 2 = 1 2 {(, , 2) 1} = 1 = 2
74
5. Star:The star of a DFA language is a DFA language
= () where = (, , , , )
= ( ) = (, , , , ) where
= {} = = {(, , )} {(, , ) } = {} = {}
6. Plus:
75
II. Decidability Properties
A decision problem is a problem each in-stance of which is either false or true.
A decision algorithm is an algorithm whoseresult for each possible input is either falseor true.
A decision problem is decidable if there ex-ists a decision algorithm for it. Otherwise itis undecidable.
1. DFA membershipINSTANCE: A DFA = (, , , , )
and a word .QUESTION: Is () ?
Theorem: DFA membership is decidable.
76
Proof: Compute for the given and the ter-minating state such that . If then answer True else answer false.
2. DFA Emptiness
INSTANCE: A DFA = (, , , , ).QUESTION: Is () = ?Theorem DFA emptiness is decidable.
Proof: () = i there is no path in thestate diagram of from to a nal state. If = , then this holds immediately.Otherwise, enumerate the states that can bereached from . (Mark . Now mark all statesreachable by one transition from one of themarked states. Repeat this until no newlymarked state is introduced.The marked states are the reachable states).
77
3. DFA Universality
INSTANCE: A DFA = (, , , , ).QUESTION: Is () = ?
Theorem DFA universality is decidable.Proof:
4. DFA Containment
INSTANCE: Two DFA1 = (1, 1, 1, 1, 1) and2 = (2, 2, 2, 2, 2).
QUESTION: Is (1) (2) ?Theorem DFA containment is decidable.Proof:
(1) (2) = means that (1) (2)
78
5. DFA Equivalence
INSTANCE: Two DFA1 = (1, 1, 1, 1, 1) and2 = (2, 2, 2, 2, 2).
QUESTION: Is (1) = (2) ?
Theorem DFA equivalence is decidable.
(1) (2) ? yes(2) (1) ? yes
79
Pumping Lemma and Non-DFA Language.
The DFA Pumping LemmaLet = (, , , , ) be a DFA and let = #. For all words in () such that , can be decomposed into , forsome , , and in such that
(i) ;(ii) 1; and(iii) for all 0, is in ().
Example = (,, , , ) where = {, , }, = {, }, = {}. # = 3
Let be an arbitrary word of length #in (), e.g. = . The accepting conf.sequence for is: .So, = , = , = and () () forall 0.
80
Proof of DFA Pumping Lemma:
Let be in () with .Then has an accepting conguration se-quence
012 . . . 12 . . . . . . 1 where 0 = , .Consider the rst transitions. , 1, . . . , cannot all be distinct since there are only distinct states (by pigeonhole principle).This means that = for some 0 < .Let
= 1 . . . ,
= +1 . . . ,
= +1 . . . .
So, we have 0 ( = ) .
Since = , for any 0
81
() , since () 1, since < () () for all 0, since
0
qed.
Re-state Pumping LemmaIf is a DFA Languagethen
( = () for some of states;)for every word of length in ,there exists one decomposition = which satises
() ,() 1,() () for all 0.
82
Comments: The DFA pumping lemma showsa property of DFA languages. It can be usedpossitively; but it is mainly used negativelyto show that some languages are not in .The DFA pumping lemma gives a necessarycondition for DFA languages. The conditionis not sucient.
Review of logic:if then if then if then if then if then if then
Exampleif it is sugar then it is sweet.if it is not sweet then it is not sugar.if it is sweet then it is sugar.
So, pumping lemma can be used to showthat a language is not a DFA language, butcannot be used to show that a language is aDFA language.
83
Non-DFA Language
= { 0} is not a DFA LanguageProof (I):
Assume is a DFA language. Then = ()for some DFA = (, , , , ) with = .Consider = , .By DFA pumping lemma, there is a decom-position
=
which satises (i), (ii), and (iii).Consider all the possible decompositions
Case 1 : = , 1. But 0 = .
Case 2 : = , 1.0 = .
Case 3 : = , , 1.Then 2 = .
All the possible decompositions fail.Therefore, is not a DFA language.
84
Proof (II):. . . . . . . . . . . . . . . . . . = .Consider = in . Obviously, .By DFA pumping lemma, there is a decom-
position =
that satises (i), (ii), and (iii).The only decompositions that satisfy
(i) and (ii) are the following:
= for 1.But 0 = .So, there is no such decomposition. is not a DFA language.
(i) ;(ii) 1;
85
Notes on proving that a language is nota DFA language by pumping lemma
1) Assume L is a DFA language.
Then we have a constant .
2) Choose a word in of length .3) Consider all the possible decompositions
of . If none of them satisfy
(i), (ii), and (iii) at the same time,
then conclude that such decomposition
does not exist.
So, is not a DFA language.
86
= {2 0} is not a DFA language.Proof:
(1) Assume = () for some = (,, , , )with = .
(2) Consider = 2+1, .
(3) By DFA P.L., there is a decomposition
=
satisfying (i), (ii), and (iii).The only decompositions of which satisfy(i) and (ii) are the following:
= , 1.Notice that = 2
+1.2+1 > 2+1 2+1 > 2+1 2 = 2i.e., 2+1 > 2+1 > 2.
2+1 > > 2.
So, / . It is contrary to (iii), so isnot a DFA language.
87
6. DFA Finiteness
INSTANCE: A DFA = (,, , , )QUESTION: Is () nite?It is decidable.
Theorem () is nite i accepts no words that satisfy
< 2Proof: If: Assume accepts no words with
< 2 and () is innite. Since() is innite, it must accept some word with 2. By P.L., = with 1, and = is in (). No-tice that > . If 2,then repeat this process.Otherwise 2 > . (i.e., 2 ).This is a contradiction.
Only if: By P.L., = , 1.Since () for all 0, () is in-nite.
88
Theorem The family of DFA languages isclosed under morphisms.
Proof:
Let be a DFA language. Then there isa DFA = (,, , , ) such that () = .Let : be a morphism.We are going to show that () = { () } is a DFA language.Construct = (,, , , ) by dening(, (), ) is in i (, ) = .
is a lazy FA. So, L(M) is a DFA language.It is not dicult to show that ( ) = ().Therefore, () is a DFA language.
89
Finite Transducers and Finite Transductions(Translations)In automata and language theory, a machinewith input and output is called a transducer.
- -I in O in
A transducer is single-valued if it producesat most one output word for each input word.It is multi-valued otherwise.
A transducer denes a function : , if it is single-valued,a relation , otherwise.A function or a relation that is dened by atransducer is called a transduction (transla-tion).
90
Specically, a nite automaton with outputis called a nite transducer.
FA(DFA, NFA, or -NFA)+ output (output alphabet, output tape)= FT
Input tape
Finite control
Output tape
?
6
read-only head
write-only head
Formally, a nite transducer (FT) is a six-tuple (,,, , , ) where is an output alphabet; ({}) is a nite transitionrelation;the others are the same as in a FA.
91
A conguration is a word in .
output till now; current state; remaining input.
We write
if (, , , ) is in .
, +, are dened as usual.Given , we say that is an output for w.r.t. if
for some .Let () be the set of all outputs for , then() = { for some }.The transduction or translation dened byis () = {(, ) and ()}
92
Example :
0 0 1 1 1 2 2
i.e. 0 2Since 2 , we say (),and (, ) ().We can see that
() = {(, ) , , 0}Example
Let () = 101, () = 11.Encoding:
Decoding:
93
REGULAR EXPRESSIONS
The Second Model for Dening Languages
Example:Consider the language of all the words thatconsist of s and s and have as a sub-word.We can formally dene this language by thefollowing:(1) = { {, } and has as a
subword};(2) = () where is an NFA given bythe following diagram:
Both of the above denitions are lengthy.It can also be expressed by
([ ][ ])
94
Denition Let be an alphabet.A regular expression over is dened recur-sively:Basis: (1) ,
(2) ,(3) , where
are R.E.s over Induction Step:
If 1 and 2 are R.E.s over , then(4) [1 2],(5) [1 2],(6) 1
are R.E.s over
We usually omit .The set of all regular expressions over is
denoted by
95
[[ + ]] is the same as [[ ]]Example:
[[1
2 ]
3
4
5
] is a R.E. over {, }
We display the parsing by anexpression tree:
What language does an R.E. dene?
(0,75)
{} {}{, }
{}{, }
{, }
96
Denition Given a regular expression , thelanguage () denoted by is dened as fol-lows:Basis: (1) if = , then ;
(2) if = , then {};(3) if = , then {};
Induction Step:(4) if = [1 2], then (1) (2);(5) if = [12], then (1)(2);(6) if = 1, then ((1))
.
Properties of R.E.s: 1 2 2 1;
[1 2] 3 1 [2 3];So, [1 2] 3 1 2 3.
: [12]3 1[23];So, [12]3 123.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
Denition A language is regular i there isa regular expression such that = ().
The family of (all) regular languages isdenoted by .
Example = []. = { in {, } and contains an even
number of }.Claim: () =
Proof:(i) () , since every word in ()
contains an even number of s.(ii)Let . Then can be written as
01 . . . . . . 2, 0, 1, . . . , 2 0.So, = (01)(23) . . . . . . (2221)2. ([])() = (). ...
98
Examples = {, }.1 = { = , }.
2 = { 0 mod 3}.[[]]
3 = { has 2 or 3 with the last twoappearances nonconsecutive }
4 = { = , 1}
99
ExamplesWhat are the languages denoted by the fol-lowing R.E.s ?
1 =
2 = [ ]
3 = [ ]
4 = [ ]
100
How many languages over do R.E.s dene? = {, }
(1) Innitely many ?
(2) Countable ?
101
Regular Expression into Finite Automata
Let be a regular expression over . Thenwe can construct a -NFA such that() = (), using the following rules:(i) = .Construct such that () =
-
(ii) = .Construct such that () = {}
-
(iii) = , .Construct such that () = {}
"!
#
--
102
(iv) = [1 2].Construct such that () = (1)(2).
(v) = [12].Construct such that () = (1)(2).
(vi) = 1.Construct such that () = (1)
.
103
Example = [[ []]]Construct a FA such that () = ().
, , by (iii)
by (vi)
[] by (v)
[ ] by (iv)
[ ] by (vi)
[[ ]] by (v)
104
Theorem For , an arbitrary regular expres-sion over , the -NFA, , constructed asabove satises () = ().
Proof: Let () be the total number of , ,and operations in . We prove this theoremby induction on ().
Basis: () = 0. Then = , , or .Then clearly we have () = ().
Induction Hypothesis:Assume the claim holds for all with () , for some 0.
Induction Step:Consider an arbitrary regular expression with () = +1. Since +1 1, containsat least one operator , , or .
Case I: = 1 2. Then (1) and (2) . So, (1) = (1) and (2) =(2) by I.H.. We know the construction of = 1 2 satises () = (1) (2),and () = (1) (2)
105
Therefore, () = ().Case II: = 12
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Case III: = 1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
In each of the three cases, we have shownthat () = (). Therefore this holds forall regular expressions by the principle of in-duction. ...
106
Finite Automata into Regular Expressions
To prove that every DFA language is regularwe introduce an extension of nite automata.
Denition An extended nite automaton(EFA), , is a quintuple (, , , , ) where, , are as in -NFA, is the only nal state, = , : is a total extended transition
function.
Example of an EFA:
(, ) = (, ) = . . . . . .One nal state =
107
A conguration is in Move
if(i) = , ,(ii) (, ) = , and(iii) ().
, + are dened similarly as before.
Lemma If is a DFA, Then there is an EFA with ( ) = ().
Example DFA into EFA.
108
Example:An extended nite Automaton (EFA).M:
Check if the following words are in ()
(1)
(2)
(3)
(4)
109
State Elimination TechniqueGoal of the technique:
i.e.:
(1) EFA has 2 states
Example
110
(2) EFA has + 1 states, 2.Then eliminate a state from to form : :
Note: {, }Consider all transitions (, , )
and (, , ) :
(, ) = (, ) (, )((, ))(, )111
Example
[ ]
112
Example
113
Summary of the State Elimination Technique(0) Change FA into EFA(1) Add a new start state if the original one
has incoming transitions.(2) Add a new nal state if there are more
than one nal states originally. Old nalstates become non-nal states.
(3) Eliminate the states in {, }one by one.
(4) Eliminate the transition (, ).
114