INSTITUT FOR MATEMATIK OG DATALOGI ODENSE UNIVERSITET

Skriftlig eksamen

D M 1 5

Fredag den 19. januar 1996 kl. 9.00 - 13.00

Opgavesættet består af 6 nummererede sider og indeholder 4 opgaver. Opgaverne vægtes sådan:

• Opgave 1: 35%

• Opgave 2: 25%

• Opgave 3: 25%

• Opgave 4: 15% Alle skriftlige hjælpemidler samt brug af lommeregner er tilladt.

Opgave 1

Denne opgave handler om kontekst-fri sprog, Turing-maskiner og Miranda.

Lad Σ = {‘(’, ‘[’, ‘)’, ‘]’}. Lad G være grammatikken ({S}, Σ, P, S), hvor P består af produktionerne

S → (S)S | [S]S | λ

Lad L = L(G) være sproget genereret af G. L er mængden af korrekt balancerede parentes-strenge, der har () og [] som de to typer af “parenteser”, der er tilladt. Det er klart, at L er et kontekst-frit sprog.

Lad L′ = {w ∈ Σ^{∗} | w har lige mange ‘(’er og ‘[’er} og lad L′′ = L ∩ L′.

I nogle af de følgende spørgsmål kan det være en hjælp at forstå standardalgoritmen til genkendelse af sproget L. Denne algoritme bruger en stak. Først push’es et specielt tegn på stakken. Dette tegn kan senere bruges til at afgøre, om man har nået bunden af stakken. Derefter læses inputstrengen fra venstre mod højre. Når en ‘(’ eller en ‘[’ læses, så push’es en kopi af tegnet på stakken. Når en ‘)’ eller en ‘]’ læses, så pop’es toppen af stakken. Hvis tegnet, der pop’es af stakken matcher det tegn, der lige er læst, så skal algoritmen bare fortsætte. Hvis tegnet, der er pop’es af stakken ikke matcher det tegn, der lige er læst (eller hvis man har fået fat i tegnet, der markerer stakbunden), så standser algoritmen og strengen afvises. Det hele fortsætter indtil hele input’et er læst. Hvis stakken på det tidspunkt kun har det specielle stakbundstegn tilbage, så accepterer algoritmen. Ellers afvises strengen.

spørgsmål a

Vis, hvordan strengen ([][()])[] kan deriveres i grammatikken G.

spørgsmål b

Vis, at L′ er et kontekst-frit sprog.

spørgsmål c

Vis, at L′′ ikke er et kontekst-frit sprog.

spørgsmål d

Beskriv (gerne i ord), hvordan en Turing-maskine, der accepterer L′′, kan konstrueres. Man må gerne bruge en Turing-maskine med flere bånd (multi-tape Turing machine).

spørgsmål e

Skriv en funktion i Miranda, der tager en streng x ∈ Σ^{∗} som input og returnerer True, hvis x ∈ L′′ og False ellers.

Denne opgave handler om regulære og kontekst-fri sprog.

Følgende definition generaliserer definitionen af L fra opgave 1. Algoritmen til genkendelse af strenge i L kan nemt generaliseres. Lad r ≥ 1 og Σ_{r} = {a_{1}, a_{2}, ..., a_{r}, ā_{1}, ā_{2}, ..., ā_{r}}. Bemærk, at tegnene kommer i matchende par. Man kan tænke på a_{i}’erne som forskellige typer af venstreparenteser og på ā_{i}’erne som deres matchende højreparenteser. Dvs. at hvis r = 2, så svarer Σ_{2} nøje til Σ. Lad grammatikken G_{r} = ({S}, Σ_{r}, P_{r}, S), hvor P_{r} består af produktionerne

S → a_{i}Sā_{i}S | λ

for 1 ≤ i ≤ r. Lad L_{r} = L(G_{r}) være sproget genereret af G_{r}. L_{r} kan man tænke på som mængden af korrekt balancerede parentes-strenge med r typer parenteser. Det er klart, at L_{r} er et kontekst-frit sprog.

spørgsmål a

Bevis, at L_{r} ikke er et regulært sprog.

spørgsmål b

Angiv en standard PDA, der accepterer L_{3} (dvs. sproget med 3 typer parenteser). Husk, at en standard PDA accepterer ved sluttilstand (“final state”) og tom stak.

spørgsmål c

Bevis, at hvis u ∈ L_{r} og v ∈ L_{r}, så gælder der også, at uv ∈ L_{r}.

Denne opgave handler om PCF.

I noten af Mitchell er nogle funktioner på de naturlige tal defineret, men der er mange almindelig funktioner, der mangler. Blandt disse er større end (greater than forkortet gt), subtraher (subtract forkortet sub) og divider (divide forkortet div). Da PCF ikke har negative tal, er det naturligt at definere disse funktioner som følgende:

• gt < m, n > = \{ \begin{matrix}true, & hvis m > n \\ false, & hvis m ≤ n \end{matrix}

• sub < m, n > = \{ \begin{matrix}m − n, & hvis m ≥ n \\ 0, & hvis m < n \end{matrix}

• div < m, n > = \{ \begin{matrix}0, & hvis n = 0 \\ ⌊\frac{m}{n}⌋, & hvis n > 0 \end{matrix}

hvor ⌊\frac{m}{n}⌋ er det største heltal mindre end eller lig med m/n (dvs. at en eventuel decimaldel efter kommaet blot smides væk).

I de følgende spørgsmål må man gerne benytte funktionerne search, mult og pred, som er defineret i noten af Mitchell. Man må også gerne i et spørgsmål bruge funktioner defineret i tidligere spørgsmål, uanset om man har regnet disse spørgsmål eller ej.

spørgsmål a

Definer funktionen sub i PCF.

spørgsmål b

Definer funktionen gt i PCF.

spørgsmål c

Definer funktionen div i PCF.

Denne opgave handler om Turing-maskiner og afgørlighed.

spørgsmål a

I lærebogen af Sudkamp er L_{H} defineret som mængden af strenge R(M)w for hvilke Turing-maskinen M standser på input w, hvor R(M) er en indkoding af maskinen M. Antag, at L er et rekursivt tælleligt (recursively enumerable) sprog over Σ = {0, 1}, og at x ∈ Σ^{∗} er en fastholdt streng. Vis, hvordan man konstruerer en enkelt Turing-maskine M_{x}, der givet y ∈ Σ^{∗} som input

• accepterer, hvis x ∈ L_{H} og y ∈ L,

• og ellers går i uendelig løkke.

spørgsmål b

Lad C være en mængde af rekursivt tællelige (recursively enumerable) sprog, sådan at C ikke er tom, og ∅ ∉ C. Bevis, at det følgende problem er uafgørlig: Givet en Turing-maskine M, afgør om M accepterer et af sprogene i C. Hjælp: man må gerne antage, at Turing-maskinen fra spørgsmål a eksisterer.