INSTITUT FOR MATEMATIK OG DATALOGI

ODENSE UNIVERSITET

Skriftlig eksamen

D M 1 5

Fredag den 21. januar 1994 kl. 9.00 - 13.00

Opgavesættet består af 5 nummererede sider og indeholder 4 opgaver. Opgaverne vægtes ens. Alle skriftlige hjælpemidler samt brug af lommeregner er tilladt.

Opgave 1

Denne opgave handler om regulære sprog. Husk, at selv om man ikke har fået regnet alle spørgsmålene, må man gerne benytte resultaterne fra tidligere spørgsmål til at løse de senere.

spørgsmål a

Tegn tilstandsgrafen for en nondeterministisk endelig automat med lambda-transitioner (NFA-λ), der accepterer sproget

{abbb} ∪ {a^{∗}b^{n} | n er lige, n ≥ 0}.

spørgsmål b

Vis, at hvis L_{1} ∪ L_{2} er et regulært sprog, og L_{1} indeholder præcis én streng, så er L_{2} også et regulært sprog.

spørgsmål c

Vis, at hvis L_{1} ∪ L_{2} er et regulært sprog, og L_{1} er endeligt, så er L_{2} også et regulært sprog.

spørgsmål d

Vis, at hvis L_{1} ∪ L_{2} er et regulært sprog, og L_{1} også er et regulært sprog, så er L_{2} ikke nødvendigvis et regulært sprog.

Denne opgave handler om kontekstfri sprog og afgørlighed. Lad Σ = {a_{1}, a_{2}, a_{3}, a_{4}, a_{5}, a_{6}, a_{7}, a_{8}}. Vi benytter notationen w^{R} til at betyde strengen w reverseret. Dvs. hvis w = d_{1}d_{2} · d_{k}, så er w^{R} = d_{k} · d_{2}d_{1}.

spørgsmål a

Lad L_{1} = {w_{1}cw_{2}cw_{2}^{R}cw_{1}^{R} | w_{1} ∈ Σ^{+}, w_{2} ∈ {1, 2, …, n}^{+}, c ∉ Σ}. Vis, at L_{1} er kontekstfrit.

spørgsmål b

Lad L_{2} = {w_{1}cw_{2}cw_{1}^{R}cw_{2}^{R} | w_{1} ∈ Σ^{+}, w_{2} ∈ {1, 2, …, n}^{+}, c ∉ Σ}. Vis, at L_{2} ikke er kontekstfrit.

spørgsmål c

Antag, at x = (x_{1}, …, x_{n}) og y = (y_{1}, …, y_{n}), hvor x_{i}, y_{i} ∈ Σ^{+}, 1 ≤ i ≤ n. Lad Gx,y = (Vx,y, Σx,y, Px,y, Sx,y), hvor

• Vx,y = {Sx,y, A, B}

• Σx,y = Σ ∪ {c} ∪ {1, 2, …, n}, hvor 1, 2, …, n, c ∉ Σ

• \begin{aligned}Px,y & = & & \{Sx,y → AcB, A → c, B → c\} \\ & & ∪ & \{A → x_{i}Ai, B → iBy_{i}^{R} | i = 1, 2, …, n\} \end{aligned}

Vis, at det generelt (dvs. for vilkårlige x og y) er uafgørligt om L(Gx,y) ∩ L_{1} = ∅.

spørgsmål d

Antag, at G = (V, Σ, P, S) er en kontekstfri grammatik. Vis, at det er afgørligt om en streng w ∈ L(G). Man skal altså beskrive en algoritme, der tager en grammatik G og en streng w som input og som så svarer på om w ∈ L(G).

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.

Denne opgave handler om lambda-kalkylen. Man må gerne benytte sig af udtryk, man allerede kender fra lærebogen. Dvs. pair, h, t, T, F, if-then-else, Y, samt Church indkodningen af heltal med udtrykkene succ, zero og pred. Udtrykket pred er også omtalt på ugeseddel 27, men alt man behøver at vide er, at pred c_{i} = c_{i−1} for i ≥ 1. Bemærk, at det sidste spørgsmål er uafhængigt af de forgående.

spørgsmål a

Vi vil nu gerne repræsentere lister i lambda-kalkylen. Vi bruger notationen [M_{1}, …, M_{n}] for indkodningen af listen med elementerne M_{1} til M_{n}. Indkodningen defineres nu rekursivt som følger:

[M] = M [M_{1}, M_{2}, …, M_{n}] = pair M_{1} [M_{2}, …, M_{n}]

For eksempel indkodes listen bestående af de tre elementer a, b og c som pair a pair b c. Angiv et lambda-udtryk, der tager en liste som argument, og som giver det femte element i listen. Man må gerne antage, at listerne altid er af længde mindst fem.

spørgsmål b

Angiv et lambda-udtryk P, der tager en liste l og et Church-indkodet tal c_{k} som argument. Der skal gælde, at P l c_{k} giver det k’te element i listen l, hvis k ∈ {1, 2, …, |l|}, hvor |l| er længden af listen l.

spørgsmål c

Antag, at der findes et lambda-udtryk single, for hvilket der gælder, at single l reducerer til T, hvis l er en liste med kun ét element, og single l reducerer til F ellers. Angiv et lambda-udtryk concat, der kan konkatenere to ikke-tomme lister. Dvs. at concat l_{1} l_{2} skal reducere til en liste af alle elementerne i l_{1} fulgt af alle elementerne i l_{2}.

spørgsmål d

Angiv et lambda-udtryk A uden frie variabler, for hvilket der gælder, at A x = x A for alle x. Husk, at F V (A) = ∅ er definitionen på, at A er uden frie variabler.