Institut for Matematik og Datalogi Odense Universitet

{May 10, 1995 \atop JFB}

DM15 – F95 – Week 29

Lecture, May 8

We covered up through section 2.5.2 in the second chapter of Mitchell’s monograph.

Lecture, May 15

We will continue on the second chapter of Mitchell’s monograph, probably covering through section 2.5.1.

Lecture, May 22

We will do a review of the course.

Problems from previous exams - to be discussed on May 29

Opgave 1

Denne opgave omhandler sprog over alfabetet {a}.

spørgsmål a

Konstruer en nondeterministisk endelig automat (NFA), der accepterer sproget givet ved det regulære udtryk λ ∪ a ∪ (aa(aaa)^{∗}) ∪ (aaa(aaa)^{∗}).

spørgsmål b

Antag, at L er et sprog over alfabetet {a} og antag at u_{1}, u_{2}, u_{3}, … er alle (muligvis uendeligt mange) strenge i L skrevet op i voksende længder. Mere formelt kan man formulere dette:

∀i ≥ 1: length(u_{i}) < length(u_{i+1})

Da kaldes L for ultimativt periodisk, hvis og kun hvis der eksisterer positive heltal n og p, sådan at

∀i ≥ n: length(u_{i+1}) − length(u_{i}) = length(u_{i+p+1}) − length(u_{i+p})

Det vil altså sige, at fra et eller andet tidspunkt, n, begynder strengenes længde at vokse med et mønster, der gentager sig med perioden p.

F.eks. er

E = {λ, a, aa, aaa, aaaaa, aaaaaa, aaaaaaaa, aaaaaaaaa, …}

svarende til længderne 0, 1, 2, 3, 5, 6, 8, 9, 11, 12, 14, 15, … ultimativt periodisk. Man kan f.eks. anvende n = 3 og p = 2 for at indse dette. Så ser man nemlig, at 3 − 2 = 6 − 5 og 5 − 3 = 8 − 6 osv. Vis, at ethvert ultimativt periodisk sprog over {a} er regulært. Hjælp: Bemærk, at E kan skrives:

{λ, a} ∪ ({aa, aaaaa, aaaaaaaa, …} ∪ {aaa, aaaaaa, aaaaaaaaa, …})

spørgsmål c

Følgende kontekstfri grammatik G genererer også sproget E. Grammatikken er defineret ved G = ({S, A, B, C, P }, {a}, P, S), hvor P indeholder produktionerne:

\begin{matrix}S → A & A → a & B → C & C → aaP & P → aaaP \\ S → ABC & A → λ & C → λ & C → aaaP & P → λ \end{matrix}

Konstruer en grammatik G′ ved anvendelse af teknikken i Sudkamp Theorem 5.1.5 side 103, sådan at følgende er opfyldt:

• startsymbolet i G′ er ikke-rekursivt (nonrecursive).

• G′ er ikke-sammentrækkende; bortset fra startsymbolet (essentially noncontracting).

• L(G′) = L(G).

Man må ikke anvende ad hoc metoder, men skal bruge metoden fra Sudkamp.

Opgave 2

Betragt sproget L_{1} = {a^{2i}b^{i}c^{2i} | i ≥ 0}. Dette sprog indeholder bl.a. strengene λ, aabcc og aaaabbcccc.

spørgsmål a

Vis, at L_{1} ikke er kontekstfrit.

spørgsmål b

Lad nu L_{2} være ligesom L_{1} bortset fra, at alle a’er erstattes af 01, alle b’er erstattes af 10, og alle c’er erstattes også af 10. Vi vil bruge notationen L_{2} = L_{1}[a ← 01, b ← 10, c ← 10] for denne transformation. De tre eksempelstrenge ovenfor vil altså give anledning til, at strengene λ, 0101101010 og 01010101101010101010 ligger i L_{2}. Vis, at L_{2} er kontekstfrit.

spørgsmål c

Antag, at vi har en Turingmaskine M = (Q, {a, b}, {a, b, B}, δ, q_{0}). Gør rede for, hvordan man skal definere en ny Turingmaskine M′ = (Q′, {0, 1}, {0, 1, B}, δ′, q′_{0}), sådan at L(M′) = L(M)[a ← 01, b ← 10]. Hvis det er nogen hjælp, må man gerne selv bestemme, hvor på båndet inputstrengen placeres.

spørgsmål d

Vis, at der ikke findes nogen algoritme, der givet en Turingmaskine som input afgør, om Turingmaskinen skriver strengen 111 (det vil altså sige, om der på noget tidspunkt findes tre ettaller i træk på båndet).

Opgave 3

I denne opgave skal man implementere et regelsystem i Miranda. Et minisystem består af et alfabet Σ og en mængde regler P på formen x → y, hvor x ∈ Σ og y ∈ Σ^{∗}. Som sædvanlig betyder x ⇒^{∗} y, at y kan deriveres fra x gennem et endeligt antal anvendelser af reglerne i systemet. For eksempel, hvis Σ = {a, b} og P = {a → aba, b → bb, a → b, a → λ}, så har vi

abaa ⇒ abaaba ⇒ abaabba ⇒ abaabb ⇒ bbaabb, så abaa ⇒^{∗} bbaabb.

Vi benytter følgende typedefinitioner i Miranda:

• alphabet == char

• rule == (char,[char])

• mini system == [rule]

I alle delspørgsmålene skal man angive typen af de funktioner, man skriver. Husk, at selv om man ikke har fået regnet alle spørgsmålene, må man gerne benytte funktionerne fra tidligere spørgsmål til at løse de senere. I de spørgsmål, hvor svaret er en liste af strenge, må denne liste gerne indeholde dubletter.

spørgsmål a

Opskriv P fra eksemplet ovenfor i Miranda i overensstemmelse med typedefinitionerne.

spørgsmål b

Skriv en funktion step, sådan at resultatet af step s r er en liste af alle de strenge, der kan nås i ét skridt fra strengen s gennem anvendelse af reglen r. For eksempel, hvis s er bab, og r er b → bb, så skal resultatet være en liste bestående af de to strenge bbab og babb.

spørgsmål c

Skriv en funktion step all, sådan at resultatet af step all s m er en liste af alle de strenge, der kan nås i ét skridt fra strengen s gennem anvendelse af en eller anden regel i minisystemet m.

spørgsmål d

Skriv en funktion generate, sådan at generate s m producerer en liste af alle mulige strenge, der kan nås i ét eller flere skridt fra strengen s gennem anvendelse af regler i minisystemet m. Bemærk, at denne liste muligvis er uendelig lang. Det kræves, at enhver streng, der kan nås i ét eller flere skridt, vil blive genereret på et eller andet tidspunkt.