[PDF] [PDF] Finite-state automata - Jeff Erickson

and that transitions among those states based on sequence of input symbols Finite-state machines are also known as deterministic finite-state automata, 



Previous PDF Next PDF





Finite State Automata and Regular Languages

Finite-state automata or finite automata for short, are the simplest automata (see Fig Definition 3 7 A deterministic finite automaton (DFA), denoted by M, is



[PDF] Finite-state automata - Jeff Erickson

and that transitions among those states based on sequence of input symbols Finite-state machines are also known as deterministic finite-state automata, 



[PDF] Finite-State Automata and Algorithms

Finite-state automata (FSA) – What for? – Recap: Chomsky hierarchy of grammars and languages – FSA, regular languages and regular expressions



[PDF] Finite Automata

Finite State Automata (FSA) Deterministic On each input there is one and only one state to which the automaton can transition from its current state



[PDF] Finite State Automata and Image Recognition - CEUR-WSorg

We assume that the reader is familiar with the elementary facts about finite automata and regular sets, see e g [4] A finite automaton is displayed by its diagram 



[PDF] Languages (Finite State Machines) Carol Zander

When they have a transition for every character in the input alphabet, they are called deterministic finite automata (DFA) Formally, a finite state automaton consists 



[PDF] Finite Automata

“Program” prescribes how symbols read affect current state Final state is state FA is in when finished read- ing the input string There are accept states (double 



[PDF] Finite State Automata and Regular Expressions - UW-Madison

10,5 Figure 13 1: The transition diagram for the vending machine M Before we define a finite state automaton more formally, let's see another example Example  



Mathematical logic and quantum finite state automata

computation, it is promising to study the relation between quantum finite-state automata and mathematical logic After a brief introduction to the connection 

[PDF] finland emergency medical services

[PDF] fintech 2019

[PDF] fintech in india

[PDF] fintech investment in india 2019

[PDF] fintech ranking

[PDF] fintech startups

[PDF] fip travel

[PDF] fipy: partial differential equations with python

[PDF] fir and iir filters pdf

[PDF] fir copy sample

[PDF] fir filter applications ppt

[PDF] fir filter design

[PDF] fir filter design matlab

[PDF] fir filter design based on fpga pdf

[PDF] fir filter design lecture notes pdf

Models of Computation Lecture 3: Finite-State Machines [Sp"?8] Life only avails, not the having lived. Power ceases in the instant of repose; it resides in the moment of transition from a past to a new state, in the shooting of the gulf, in the darting to an aim. - Ralph Waldo Emerson, "Self Reliance",Essays, First Series(1841) O Marvelous! what new configuration will come next?

I am bewildered with multiplicity.

- William Carlos Williams, "At Dawn" (1914)

3 Finite-State Machines

3.? IntuitionSuppose we want to determine whether a given stringw[1..n]of bits represents a multiple of 5

in binary. After a bit of thought, you might realize that you can read the bits inwone at a time,

from left to right, keeping track of the value modulo 5 of the prefix you have read so far.MultipleOf5(w[1..n]):rem 0

fori 1ton rem (2rem+w[i])mod 5 ifrem=0 returnTrue else returnFalse Aside from the loop indexi, which we need just to read the entire input string, this algorithm has a single local variablerem, which has only four different values:0,1,2,3, or4. This algorithm already runs inO(n)time, which is the best we can hope for-after all, we have to read every bit in the input-but we can speed up the algorithmin practice. Let"s define a changeortransitionfunction:f0,1,2,3,4gf0,1g ! f0,1,2,3,4gas follows: (q,a) = (2q+a)mod 5. (Here I"m implicitly converting the symbols0and1to the corresponding integers0and1.) Since we already know all values of the transition function, we can store them in a precomputed table, and then replace the computation in the main loop ofMultipleOf5with a simple array lookup. We can also modify the return condition to check for different values modulo 5. To be completely general, we replace the final if-then-else lines with another array lookup, using an arrayA[0..4]of booleans describing which final mod-5 values are "acceptable". After both of these modifications, our algorithm looks like one of the following, depending on

whether we want something iterative or recursive (withq=0in the initial call):DoSomethingCool(w[1..n]):q 0

fori 1ton q [q,w[i]] returnA[q]DoSomethingCool(q,w):ifw=" returnA[q] else decomposew=ax returnDoSomethingCool((q,a),x)©Copyright 2018 Jeff Erickson. This work is licensed under a Creative Commons License ( Free distribution is strongly encouraged; commercial distribution is expressly forbidden. See for the most recent revision.

Models of Computation Lecture 3: Finite-State Machines [Sp"?8]If we want to use our newDoSomethingCoolalgorithm to implementMultipleOf5, we

simply give the arraysandAthe following hard-coded values: q[q,0][q,1]A[q]0 0 1True1 2 3False2 4 0False3 1 2False4 3 4False We can also visualize the behavior ofDoSomethingCoolby drawing a directed graph, whose vertices represent possible values of the variableq-the possiblestatesof the algorithm-and whose edges are labeled with input symbols to represent transitions between states. Specifically, the graph includes the labeled directed edgepa!qif and only if(p,a) =q. To indicate the proper return value, we draw the "acceptable" final states using doubled circles. Here is the resulting graph forMultipleOf5:

011110000110234State-transition graph forMultipleOf5

If we run theMultipleOf5algorithm on the string00101110110(representing the number

374 in binary), the algorithm performs the following sequence of transitions:

0

0!00!01!10!21!01!11!30!11!31!20!4

Because the final state is not the "acceptable" state0, the algorithm correctly returnsFalse. We can also think of this sequence of transitions as a walk in the graph, which is completely determined by the start state0and the sequence of edge labels; the algorithm returnsTrueif and only if this walk ends at an "acceptable" state.

3.2 Formal Definitions

The object we have just described is an example of afinite-state machine. A finite-state machine is a formal model of any system/machine/algorithm that can exist in a finite number ofstates and that transitions among those states based on sequence ofinputsymbols. Finite-state machines are also known asdeterministic finite-state automata, abbreviated DFAs. The word "deterministic" means that the behavior of the machine is completelydetermined by the input string; we"ll discuss nondeterministic automata in the next lecture. The word "automaton" (the singular of "automata") comes from ancient GreekaÎtìmatocmeaning "self- acting", from the rootsaÎtì-("self") and-matoc("thinking, willing", the root of Latinmentus). Formally, every finite-state machine consists of five components: •An arbitrary finite set, called theinput alphabet. 2 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] •Another arbitrary finite setQ, whose elements are calledstates.ⁱ •An arbitrarytransitionfunction:Q!Q. •Astart states2Q.

•A subsetAQofaccepting states.The behavior of a finite-state machine is governed by aninput stringw, which is a finite

sequence of symbols from the input alphabet. The machinereadsthe symbols inwone at a time in order (from left to right). At all times, the machine has acurrent stateq; initiallyqis the machine"s start states. Each time the machine reads a symbolafrom the input string, its current statetransitionsfromqto(q,a). After all the characters have been read, the machine acceptswif the current state is inAandrejectswotherwise. In other words, every finite state machine runs the algorithmDoSomethingCool! More formally, we extend the transition function:Q!Qof any finite-state machine to a function:Q!Qthat transitions onstringsas follows: (q,w):=( qifw=", ((q,a),x)ifw=ax. Finally, a finite-state machineacceptsa stringwif and only if(s,w)2A, andrejectsw otherwise. (Compare this definition with the recursive formulation ofDoSomethingCool!) For example, our finalMultipleOf5algorithm is a DFA with the following components: •input alphabet:=f0,1g •state set:Q=f0,1,2,3,4g •transition function:(q,a) = (2q+a)mod 5 •start state:s=0 •accepting states:A=f0g This machine rejects the string00101110110, because (0,00101110110) =((0,0),0101110110) =(0,0101110110) =((0,0),101110110) =(0,101110110) =((0,1),01110110) =... =(1,110) =((1,1),10) =(3,10) =((3,1),0) =(2,0) =((3,0),") =(4,") =462A.ⁱ

It"s unclear why we use the letterQto refer to the state set, and lower-caseqto refer to a generic state, but that

is now the firmly-established notational standard. Although the formal study of finite-state automata began much

earlier, its modern formulation was established in a ?959 paper by Michael Rabin and Dana Scott, for which they won

the Turing award. Rabin and Scott called the set of statesS, used lower-casesfor a generic state, and called the start

states0. On the other hand, in the ?936 paper for which the Turing award was named, Alan Turing usedq1,q2,...,qR

to refer to states (or "m-configurations") of a generic Turing machine. Turing may have been mirroring the standard

notationQfor configuration spaces in classical mechanics, also of uncertain origin. 3 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] We have already seen a more graphical representation of this entire sequence of transitions: 0

0!00!01!10!21!01!11!30!11!31!20!4The arrow notation is easier to read and write for specific examples, but surprisingly, most people

actually find the more formal functional notation easier to use in formal proofs. Try them both! We can equivalently define a DFA as a directed graph whose vertices are the statesQ, whose edges are labeled with symbols from, such that every vertex has exactly one outgoing edge with each label. In our drawings of finite state machines, the start statesis always indicated by an incoming arrow, and the accepting statesAare always indicted by doubled circles. By induction, for any stringw2, this graph contains a unique walk that starts atsand whose edges are labeled with the symbols inwin order. The machine acceptswif this walk ends at an accepting state. This graphical formulation of DFAs is incredibly useful for developing intuition and even designing DFAs. For proofs, it"s largely a matter of taste whether to write in terms of extended transition functions or labeled graphs, but (as much as I wish otherwise) I actually find it easier to writecorrectproofs using the functional formulation.

3.3 Another Example

The following drawing shows a finite-state machine with input alphabet=f0,1g, state set Q=fs,tg, start states, a single accepting statet, and the transition function (s,0) =s,(s,1) =t,(t,0) =t,(t,1) =s. 0011 stA simple finite-state machine. Forexample, thetwo-statemachineMatthetopofthispageacceptsthestring00101110100 after the following sequence of transitions: s

0!s0!s1!t0!t1!s1!t1!s0!s1!t0!t0!t.

The same machineMrejects the string11101101after the following sequence of transitions: s

1!t1!s1!t0!t1!s1!t0!t1!s.

Finally,Mrejects the empty string, because the start statesis not an accepting state. From these examples and others, it is easy to conjecture that the language ofMis the set of all strings of0s and1s with an odd number of1s. So let"s prove it!

Proof (tedious case analysis):

Let#(a,w)denote the number of times symbolaappears in stringw. We will prove the following stronger claims by induction, for any stringw. (s,w) =¨sif#(1,w)is even tif#(1,w)is oddand(t,w) =¨tif#(1,w)is even sif#(1,w)is odd Let"s begin. Letwbe an arbitrary string. Assume that for any stringxthat is shorter thanw, we have(s,x) =sand(t,x) =tifxhas an even number of1s, and(s,x) =tand (t,x) =sifxhas an odd number of1s. There are five cases to consider. 4 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] •Ifw=", thenwcontains an even number of1s and(s,w) =sand(t,w) =tby definition. •Supposew=1xand#(1,w)is even. Then#(1,x)is odd, which implies (s,w) =((s,1),x)by definition of =(t,x)by definition of =sby the inductive hypothesis (t,w) =((t,1),x)by definition of =(s,x)by definition of =Tby the inductive hypothesis Since the remaining cases are similar, I"ll omit the line-by-line justification. •Ifw=1xand#(1,w)is odd, then#(1,x)is even, so the inductive hypothesis implies (s,w) =((s,1),x) =(t,x) =t (t,w) =((t,1),x) =(s,x) =s •Ifw=0xand#(1,w)is even, then#(1,x)is even, so the inductive hypothesis implies (s,w) =((s,0),x) =(s,x) =s (t,w) =((t,0),x) =(t,x) =t Finally, ifw=0xand#(1,w)is odd, then#(1,x)is odd, so the inductive hypothesis implies (s,w) =((s,0),x) =(s,x) =t (t,w) =((t,0),x) =(t,x) =sƒ Notice that this proof containsjQj2jj+jQjseparate inductive arguments. For every pair of statespandq, we must argue about the language of all stringswsuch that(p,w) =q, and we must consider every possible first symbol inw. We must also argue about(p,")for every

statep. Each of those arguments is typically straightforward, but it"s easy to get lost in the deluge

of cases. For this particular proof, however, we can reduce the number of cases by switching from tail recursion toheadrecursion. The following identity holds for all stringsx2and symbols a2:

(q,xa) =((q,x),a)We leave the inductive proof of this identity as a straightforward exercise (hint, hint).

Proof (clever renaming, head induction):

Let"s rename the states with the integers0and1

instead ofsandt. Then the transition function can be described concisely as(q,a) = (q+a)mod 2.We claim that for every stringw, we have(0,w) =#(1,w)mod 2. Letwbe an arbitrary string, and assume that for any stringxthat is shorter thanwthat (0,x) =#(1,x)mod 2. There are only two cases to consider: eitherwis empty or it isn"t. •Ifw=", then(0,w) =0=#(1,w)mod 2by definition. 5 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] •Otherwise,w=xafor some stringxand some symbola, and we have (0,w) =((0,x),a)by definition of =(#(1,x)mod 2,a)by the inductive hypothesis = (#(1,x)mod 2+a)mod 2by definition of = (#(1,x)+a)mod 2by definition ofmod 2 = (#(1,x)+#(1,a))mod 2because#(1,0) =0and#(1,1) =1 = (#(1,xa))mod 2by definition of #

= (#(1,w))mod 2becausew=xaƒHmmm. This "clever" proof is certainly shorter than the earlier brute-force proof, but is it

actuallybetter? Simpler? More intuitive? Easier to understand? I"m skeptical. Sometimes brute force really is more effective.

3.4 Real-World Examples

Finite-state machines were first formally defined in the mid-20th century, but people have been building automata for centuries, if not millennia. Many of the earliest records about automata are clearly mythological-for example, the brass giant Talus created by Hephaestus to guard Crete against intruders-but others are more believable, such as King-Shu"s construction of a flying magpie from wood and bamboo in China around 500bce. Perhaps the most common examples of finite-state automata areclocks. For example, the Swiss railway clock designed by Hans Hilfiker in ?944 has hour and minute hands that can indicate any time between ?:00 and ?2:59. The minute hands advance discretely once per minute

when they receive an electrical signal from a central master clock.²Thus, a Swiss railway clock is

a finite-state machine with 720 states, one input symbol, and a simple transition function:

Q=f(h,m)j0h11and0m59g

=ftickg ((h,m),tick) =8 :(h,m+1)ifm<59 (h+1,0)ifh<11andm=59 (0,0)ifh=11andm=59 This clock doesn"tquitematch our abstraction, because there"s no "start" state or "accepting" states, unless perhaps you consider the "accepting" state to be the time when your train arrives. A more playful example of a finite-state machine is theRubik"s cube, a well-known mechanical puzzle invented independently by Ernő Rubik in Hungary and Terutoshi Ishigi in Japan in the mid- ?970s. Thispuzzlehasprecisely5?9,024,039,293,878,272,000distinctconfigurations. Intheunique solvedconfiguration, each of the six faces of the cube shows exactly one color. We can change the configuration ofthe cubeby rotatingoneofthe sixfaces of thecubeby 90degrees, either clockwise or counterclockwise. The cube has six faces (front, back, left, right, up, and down), so there are

exactly twelve possible turns, typically represented by the symbolsR,L,F,B,U,D,¯R,¯L,¯F,¯B,¯U,¯D,

where the letter indicates which face to turn and the presence or absence of a bar over the letter²

A second hand was added to the Swiss Railway clocks in the mid-?950s, which sweeps continuously around the

clock in approximately 58½seconds and then pauses at ?2:00 until the next minute signal "to bring calm in the last

moment and ease punctual train departure". Let"s ignore that. 6

Models of Computation Lecture 3: Finite-State Machines [Sp"?8]indicates turning counterclockwise or clockwise, respectively. Thus, we can represent a Rubik"s

cube as a finite-state machine with 5?9,024,039,293,878,272,000 states and an input alphabet with ?2 symbols; or equivalently, as a directed graph with 5?9,024,039,293,878,272,000 vertices, each with ?2 outgoing edges. In practice, the number of states isfartoo large for us to actually draw the machine or explicitly specify its transition function; nevertheless, the number of states is still finite. If we let the start statesand the sole accepting state be the solved state, then the language of this finite state machine is the set of all move sequences that leave the cube unchanged.Three finite-state machines.

3.5 A Brute-Force Design Example

As usual in algorithm design, there is no purely mechanical recipe-noautomaticmethod-no algorithm-for building DFAs in general. Here I"ll describe one systematic approach that works reasonably well, although it tends to produce DFAs with many more states than necessary.

3.5.? DFAs are Algorithms

The basic approach is to try toconstruct an algorithmthat looks likeMultipleOf5: A simple for-loop through the symbols, using aconstantnumber of variables, where each variable (except the loop index) has only aconstantnumber of possible values. Here, "constant" means an actual number that is not a function of the input sizen. You should be able to compute the number of possible values for each variableat compile time. For example, the following algorithm determines whether a given string in=f0,1g contains the substring11.Contains11(w[1..n]):found False fori 1ton ifi=1 last2 w[1] else last2 w[i1]w[i] iflast2=11 found True returnfoundAside from the loop index, this algorithm has exactly two variables. 7 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] •A boolean flagfoundindicating whether we have seen the substring11. This variable has exactly two possible values:TrueandFalse. A stringlast2containing the last (up to) three symbols we have read so far. This variable has exactly 7 possible values:",0,1,00,01,10, and11. Thus, altogether, the algorithm can be in at most27=14possible states, one for each possible pair(found,last2). Thus, we can encode the behavior ofContains??as a DFA with fourteen states, where the start state is(False,")and the accepting states are all seven states of the form (True,). The transition function is described in the following table (split into two parts to save space): q[q,0][q,1](False,") (False,0) (False,1) (False,0) (False,00) (False,01) (False,1) (False,10) (True,11)(False,00) (False,00) (False,01) (False,01) (False,10) (True,11) (False,10) (False,00) (False,01) (False,11) (False,10) (True,11)q[q,0][q,1](True,") (True,0) (True,1) (True,0) (True,00) (True,01) (True,1) (True,10) (True,11)(True,00) (True,00) (True,01) (True,01) (True,10) (True,11) (True,10) (True,00) (True,01) (True,11) (True,10) (True,11) For example, given the input string1001011100, this DFA performs the following sequence of transitions and then accepts. (False,01)0!(False,10)1!(False,01)1!

3.5.2 ...but Algorithms can be Wasteful

You can probably guess that the brute-force DFA we just constructed has considerably more states than necessary, especially after seeing its transition graph:

0110F,!",!F,0F,1",0",1F,00F,10F,01F,11",00",10",01",11111111011000101000100001Our brute-force DFA for strings containing the substring11

For example, the state(False,11)has no incoming transitions, so we can just delete it. (This state would indicate that we"ve never read11, but the last two symbols we read were11, which 8 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] Corollary 3.5.LetLandL0be arbitrary automatic languages. •L•L0is automatic.

•Lis automatic.These results give us several options to prove that a given languages is regular or automatic.

We can either (?) build a regular expression that describes the language, (2) build a DFA that accepts the language, or (3) build the language from simpler pieces from other regular/automatic languages. (Later we"ll see a fourth option, and possibly even a fifth.)

3.8 Proving a Language is Not Regular

But now suppose we"re faced with a languageLwhere none of these techniques seem to work. How would we proveLisnotregular? By Theorem??, it suffices to prove that there is no finite-state automaton that acceptsL. Equivalently, we need to prove that any automaton that acceptsLrequires infinitely many states. That may sound tricky, what with the "infinitely many", but there"s actually a fairly simple technique to prove exactly that.

3.8.? Distinguishing Suffixes

Perhaps the single most important feature of DFAs is that they have no memory other than the current state. Once a DFA enters a particular state, allfuturetransitions depend only on that state andfutureinput symbols;pastinput symbols are simply forgotten. For example, consider our very first DFA, which accepts the binary representations of integers divisible by 5.

011110000110234DFA accepting binary multiples of 5.

The strings0010and11011both lead this DFA to state2, although they follow different transitions to get there. Thus, for any stringz, the strings0010zand11011zalso lead to the same state in this DFA. In particular,0010zleads to the accepting state if and only if11011z leads to the accepting state. It follows that0010zis divisible by 5 if and only if11011zis divisible by 5. More generally, any DFAM= (,Q,s,A,)defines an equivalence relation over, where two stringsxandyare equivalent if and only if they lead to the same state, or more formally, if (s,x) =(s,y). Ifxandyare equivalent strings, then for any stringz, the stringsxzand yzare also equivalent. In particular,Macceptsxzif and only ifMacceptsyz. Thus, ifLis the language accepted byM, thenxz2Lif and only ifyz2L. In short, if themachinecan"t distinguish betweenxandy, then thelanguagecan"t distinguish betweenxzandyzfor any suffixz. Now let"s turn the previous argument on its head. LetLbe an arbitrary language, and letx andybe arbitrary strings. Adistinguishing suffixforxandy(with respect toL) is a third stringzsuch thatexactly oneof the stringsxzandyzis inL. Ifxandyhave a distinguishing ?3

Models of Computation Lecture 3: Finite-State Machines [Sp"?8]suffixz, then inanyDFA that acceptsL, the stringsxzandyzmust lead to different states, and

therefore the stringsxandymust lead to different states! For example, letL5denote the the set of all strings overf0,1gthat represent multiples of 5 in binary. Then the stringsx=01andy=0011are distinguished by the suffixz=01: xz=01•01=01012L5(because01012=5) It follows that ineveryDFA that acceptsL5, the strings01and0011lead to different states. Moreover, since neither01nor0011belong toL5, every DFA that acceptsL5must have at least twonon-acceptingstates, and therefore at least three states overall.

3.8.2 Fooling Sets

Afooling setfor a languageLis a setFof strings such thateverypair of strings inFhas a distinguishing suffix. For example,F=f0,1,10,11,100gis a fooling set for the languageL5of binary multiples of 5, because each pair of strings inFhas a distinguishing suffix: •0distinguishes0and1; •0distinguishes0and10; •0distinguishes0and11; •0distinguishes0and100; •1distinguishes1and10; •01distinguishes1and11; •01distinguishes1and100; •1distinguishes10and11; •1distinguishes10and100; •11distinguishes11and100. Each of these five strings leads to a different state, foranyDFAMthat acceptsL5. Thus, everyDFA that accepts the languageL5has at least five states. And hey, look, we already have a DFA forL5with five states, so that"s the best we can do! More generally, foranylanguageL, andanyfooling setFforL,everyDFA that acceptsLmust have at leastjFjstates. In particular, if the fooling setFisinfinite, then every DFA that acceptsL must have aninfinitenumber of states. But there"s no such thing as afinite-state machine with aninfinitenumber of states! IfLhas an infinite fooling set, thenLis not regular. This is arguably both the simplest and most powerful method for proving that a language is non-regular. Here are a few canonical examples of the fooling-set technique in action.

Lemma 3.6.The languageL=f0n1njn0gis not regular.

Proof:Consider the infinite setF=f0njn0g, or more simplyF=0.

Letxandybe arbitrary distinct strings inF.

The definition ofFimpliesx=0iandy=0jfor some integersi6=j. ?4 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] The suffixz=1idistinguishesxandy, becausexz=0i1i2L, butyz=0j1i62L. Thus,everypair of distinct strings inFhas a distinguishing suffix.

In other words,Fis a fooling set forL.

BecauseFis infinite,Lcannot be regular.ƒ

Lemma 3.7.The languageL=fwwRjw2gof even-length palindromes is not regular. Proof:LetFdenote the set01, and letxandybe arbitrary distinct strings inF. Then we must havex=0i1andy=0j1for some integersi6=j. The suffixz=10idistinguishesx andy, becausexz=0i110i2L, butyz=0i110j62L. We conclude thatFis a fooling set forL.

BecauseFis infinite,Lcannot be regular.ƒ

Lemma 3.8.The languageL=f02njn0gis not regular.

Proof (F=L):

Letxandybe arbitrary distinct strings inL. Then we must havex=02i andy=02jfor some integersi6=j. The suffixz=02idistinguishesxandy, because xz=02i+2i=02i+12L, butyz=02i+2j62L. We conclude thatLitself is a fooling set forL.

BecauseLis infinite,Lcannot be regular.ƒ

Proof (F=0):Letxandybe arbitrary distinct strings in0. Then we must havex=0iand y=0j for some integersi6=j; without loss of generality, assumeij. Consider the suffixz=02ki. We havexz=0i+(2ki)=02k2L, but yz=0j+(2ki)=02ki+j62L, because 2 k<2ki+j<2k+j<2k+2k=2k+1. Thus,zis a distinguishing suffix forxandy. We conclude that0is a fooling set forL. Because

Lis infinite,Lcannot be regular.ƒ

Proof (F=0again):

Letxandybe arbitrary distinct strings in0. Then we must havex=0i andy=0jfor some integersi6=j; without loss of generality, assumeij. Consider the suffixz=02kj. We havexz=0i+(2kj)=02kj+i62L, because 2 k1<2k2k1+i<2kj+i<2k. On the other hand,yz=0j+(2kj)=02k2L. Thus,zis a distinguishing suffix forxandy. We conclude that0is a fooling set forL. BecauseLis infinite,Lcannot be regular.ƒ The previous examples show the flexibility of this proof technique; a single non-regular language can have many different infinite fooling sets,⁴and each pair of strings in any fooling set can have many different distinguishing suffixes. Fortunately, we only have to findoneinfinite setFandonedistinguishing suffix for each pair of strings inF. Lemma 3.9.The languageL=f0pjpis primegis not regular.⁴

At some level, this observation is trivial. IfFis an infinite fooling set forL, then every infinite subset ofFis also

an infinite fooling set forL! ?5 Models of Computation Lecture 3: Finite-State Machines [Sp"?8] Proof (F=0):Again, we use0as our fooling set, but but the actual argument is somewhat more complicated than in our earlier examples. Letxandybe arbitrary distinct strings in0. Then we must havex=0iandy=0jfor some integersi6=j; without loss of generality, assume thatipis not, there must be a positive integerkpsuch thatp+(k1)(ji)is prime butp+k(ji)is not. Then I claim that the suffixz=0p+(k1)jkidistinguishesxandy: xz=0i0p+(k1)jki=0p+(k1)(ji)2Lbecausep+(k1)(ji)is prime; yz=0j0p+(k1)jki=0p+k(ji)62Lbecausep+k(ji)is not prime. (BecauseiProof (F=L): Letxandybe arbitrary distinct strings inL. Then we must havex=0pand y=0qfor some primesp6=q; without loss of generality, assumepp is not prime, there must be a non-negative integerk