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