Institut for Matematik og Datalogi Odense Universitet February 24, 1995

JFB

DM15 – F95 – Week 19

Lecture, February 20

We finished through section 9.5 and began section 9.6 in chapter 9 in Sudkamp.

Lecture, February 27

We will finish chapters 9 and 10 in Sudkamp.

Lecture, March 6

We will cover section 6.9 and begin chapter 11 in Sudkamp.

Problems to be discussed in week 10

• Do problem 20 on page 234 of Sudkamp.

• Do problem 25 on page 234 of Sudkamp.

• A year ago, the following item appeared in the newsgroup comp.theory. As someone suggested, it seems like a homework problem. How would you answer this news? (Clearly, there is a typo and w should be a string over the alphabet {a, b}.

From: adamy@cs.bu.edu (Adam Yen) Date: 17 Feb 1994 08:09:32 GMT Newsgroups: comp.theory Subject: Finite State Automaton Problem

Does anyone out there has at least a clue how to solve this problem? Construct a finite state automaton diagram that accepts the following language. L=w : w consists twice as many a’s as b’s w=string (which consist of the alphabets a and ) -Adam

• Do the following questions from a past DM15 exam: I de første to spørgsmål i denne opgave skal man implementere en simulator for deterministiske Turing-maskiner i Miranda.

En Turing-maskine-simulator tager to argumenter: en liste af transitioner for en Turing-maskine og et input til Turing-maskinen. Simulatoren skal så simulere Turing-maskinen’s opførsel på den givne input-streng. Hvis Turing-maskinen standser, så skal simulatoren returnere det, der står på båndet, når Turing-maskinen standser. Antag, at Turing-maskinen’s tilstande er af type num, og at båndsymbolerne er af type char. Antag, at 0 er starttilstanden. Så kan vi benytte følgende typedefinitioner i Miranda:

– dir ::= L | R

– transition == (num,char,num,char,dir)

– transitions == [transition]

– instdesc == (num,[char],[char],transitions)

En transition er et tupel, hvor man, givet en tilstand og et symbol under Turing-ma-skinen’s læsehoved, kan se, hvad den næste tilstand skal være, hvilket symbol Turingmaskinen skal skrive, og hvilken retning Turing-maskinen skal bevæge sig. F.eks. angiver (3,′ a′, 7,′ b′, R), at Turing-maskinen i tilstand 3 med ′a′ under læsehovedet skal skifte til tilstand 7, skrive et ′b′ og gå til højre. En øjebliksbeskrivelse (instantaneous description) består af den nuværende tilstand, en liste af symboler til venstre for læsehovedet, en liste af symbolerne under og til højre for læsehovedet samt listen af transitioner. Vi benytter også følgende funktionsdefinitioner:

– first5 (a,b,c,d,e) = a

– second5 (a,b,c,d,e) = b

– third5 (a,b,c,d,e) = c

– fourth5 (a,b,c,d,e) = d

– fifth5 (a,b,c,d,e) = e

– third4 (a,b,c,d) = c

spørgsmål a

Skriv en funktion move, sådan at resultatet af move x er den næste øjebliksbeskrivelse efter x. Typen er – move :: instdesc → instdesc. Hvis Turing-maskinen standser eller går til venstre fra den første plads på båndet, så skal tilstanden ikke ændres, men hele strengen på båndet skal stå i den første af de to lister med symbolerne på båndet, og den anden skal være tom.

spørgsmål b

Skriv en funktion run, sådan at resultatet af run x trans er hele den streng, der repræsenterer indholdet af båndet, idet Turing-maskinen standser eller går til venstre fra den første plads på båndet, når Turing-maskinen startes med x som input. Typen er – run :: [char] → transitions → [char]. Husk, at der skal være et ’B’ til venstre for x, når Turing-maskinen starter. Hvis Turing-maskinen ikke standser, så skal run x trans heller ikke standse.