INSTITUT FOR MATEMATIK OG DATALOGI ODENSE UNIVERSITET

Skriftlig eksamen

D M 1 5

Fredag den 20. januar 1995 kl. 9.00 - 13.00

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

• Opgave 1: 25%

• Opgave 2: 25%

• Opgave 3: 30%

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

Opgave 1

Denne opgave handler om regulære sprog. Lad L være den regulære mængde defineret ved udtrykket a((bab)^{∗} ∪ (baa)^{∗}).

spørgsmål a

Tegn tilstandsgrafen for en nondeterministisk endelig automat med λ-overgange (NFA-λ), der accepterer L.

spørgsmål b

Skriv et regulært udtryk for mængden \{x ∈ \{a, b\}^{∗} | ∃y ∈ L: length(x) = \frac{1}{2}length(y)\}.

spørgsmål c

Lad M = (Q, Σ, δ, q_{0}, F) være en DFA. Definer v.h.a. M en NFA-λ, der accepterer \{x ∈ Σ^{∗} | ∃y ∈ L(M): length(x) = \frac{1}{2}length(y)\}.

spørgsmål d

Vis, at der eksisterer et regulært sprog L over alfabetet {a, b}, sådan at

{x ∈ {a, b}^{∗} | ∃y ∈ L: length(x) = (length(y))^{4}}

ikke er et regulært sprog.

Opgave 2

Denne opgave handler om kontekstfri og kontekstsensitive sprog. En kontekstfri grammatik G = (V, Σ, P, S) er variabelbegrænset, hvis og kun hvis der eksisterer et heltal k ≥ 1, sådan at der for alle derivationer S ⇒^{∗} α, α ∈ (V ∪ Σ)^{∗} gælder, at der højst er k variabler i α. Et sprog L kaldes for variabelbegrænset, hvis og kun hvis der eksisterer en variabelbegrænset grammatik for L.

spørgsmål a

Lad G = ({S, X, B, C}, {a, b, c}, P, S), hvor P består af S → aaXBC

X → aaXB | λ
B → b
C → cC | λ

Er G variabelbegrænset? Hvorfor eller hvorfor ikke?

spørgsmål b

Find en kontekstfri grammatik G′, der er variabelbegrænset, selv om L(G′) er ubegrænset (d.v.s. at L(G′) indeholder uendeligt mange strenge).

spørgsmål c

Find et kontekstfrit sprog L, der ikke er variabelbegrænset. D.v.s. at man skal finde et sprog for hvilket, der ikke eksisterer nogen variabelbegrænset grammatik. Angiv sproget L v.h.a. en kontekstfri grammatik.

spørgsmål d

Find en kontekstsensitiv grammatik G = (V, Σ, P, S) for dit sprog L fra spørgsmål c, sådan at

1. hver regel har mindst én variabel på venstresiden, og

2. der for alle derivationer S ⇒^{∗} α gælder, at der højst er to variabler i α.

(Hvis du ikke har svaret på spørgsmål c, eller hvis du bare synes, at det er nemmere, så kan du bruge L = {wcwcw^{R} | w ∈ {a, b}^{∗}} i stedet for dit sprog fra spørgsmål c.)

Denne opgave handler om afgørlighed og Miranda. Husk, at hvis din løsning ligner noget i lærebogen, så er det ikke nødvendigt at kopiere det hele – bare fortæl hvilke ændringer, der er nødvendige.

spørgsmål a

Lad Σ være et alfabet, og lad {(u_{i}, v_{i}) | 1 ≤ i ≤ n} være en mængde af ordnede par, hvor u_{i}, v_{i} ∈ Σ^{+}. Det Modificerede Post Correspondence Problem (MPCP) er følgende:

Eksisterer der i_{1}, ..., i_{k}, hvor 1 ≤ i_{j} ≤ n, sådan at u_{1}u_{i_{1}}...u_{i_{k}} = v_{1}v_{i_{1}}...v_{i_{k}}?

Den eneste ændring fra det almindelige Post Correspondence Problem er, at de første strenge i MPCP skal være u_{1} og v_{1}. Vis, at MPCP er uafgørligt.

spørgsmål b

Vis, at Post Correspondence Problem er afgørligt, hvis length(u_{i}) = length(v_{i}) for 1 ≤ i ≤ n. Man skal altså beskrive en algoritme, der tager en sådan mængde af ordnede par {(u_{i}, v_{i}) | 1 ≤ i ≤ n}, hvor u_{i}, v_{i} ∈ Σ^{+}, som input, og som så svarer på, om der eksisterer k ≥ 1 og i_{1}, ..., i_{k}, hvor 1 ≤ i_{j} ≤ n, sådan at

u_{i_{1}}...u_{i_{k}} = v_{i_{1}}...v_{i_{k}}.

spørgsmål c

Post Correspondence Problem er afgørligt, hvis k er givet som en del af problemet. Nu består systemet af k og en mængde {(u_{i}, v_{i}) | 1 ≤ i ≤ n} af ordnede par, hvor u_{i}, v_{i} ∈ Σ^{+}. Man spørger, om der eksisterer i_{1}, ..., i_{k}, hvor 1 ≤ i_{j} ≤ n, sådan at

u_{i_{1}}...u_{i_{k}} = v_{i_{1}}...v_{i_{k}}.

Det er kun nødvendigt at undersøge alle muligheder, der bruger k brikker (dominoes). For eksempel, hvis mængden består af {(aaa, aa), (aa, aaaa)}, så følger bl.a:

• hvis k = 1, så er svaret “nej”.

• hvis k = 2, så er svaret “nej”.

• hvis k = 3, så er svaret “ja”, fordi (aaa, aa), (aaa, aa), (aa, aaaa), er en løsning.

• hvis k = 4, så er svaret “nej”.

Skriv en funktion combination i Miranda, sådan at resultatet af combination k xs er en liste, der består af alle mulige lister bestående af k elementer fra xs. Husk, at det er muligt for en liste at indeholde et element mere end én gang. For eksempel er combination 2 [(“aaa”, “aa”),(“aa”, “aaaa”)]

= [[(“aaa”, “aa”),(“aaa”, “aa”)],[(“aaa”, “aa”),(“aa”,”aaaa”)], [(“aa”, “aaaa”),(“aaa”, “aa”)], [(“aa”, “aaaa”),(“aa”, “aaaa”)]]

Resultatet er alle mulige kombinationer af k brikker. Typen er

• combination :: num → [([char],[char])] → [[([char],[char])]]

spørgsmål d

Skriv en funktion check i Miranda, der afgør, om en instans af Post Correspondence Problem har en løsning, der bruger præcis k brikker. Typen skal være

• check :: num → [([char],[char])] → bool

Hjælp: lav evt. først en funktion make dominoes, der udfra enhver af de lister, man får fra funktionen combination, laver et par bestående af konkatenationen af henholdsvis alle førstekomponenterne og alle andenkomponenterne. Eksempelvis skal

make dominoes (combination 2 [(“aaa”, “aa”),(“aa”, “aaaa”)]) = [(“aaaaaa”, “aaaa”),(“aaaaa”, “aaaaaa”),

(“aaaaa”, “aaaaaa”), (“aaaa”, “aaaaaaaa”)] Denne opgave handler om PCF og Miranda. Antag, at man har defineret følgende funktioner i PCF:

• En funktion pairnums af typen nat→nat→nat, sådan at pairnums er en injektiv afbildning fra N I × N I til N I − {0}. (En mulig definition er pairnums n m = (n + m) ∗ (n + m + 1)/2 + m + 1.)

• En funktion projnum_{1} af typen nat→nat, sådan at projnum_{1} (pairnums n m) = n.

• En funktion projnum_{2} af typen nat→nat, sådan at projnum_{2} (pairnums n m) = m.

Nu kan man implementere en liste, der består af naturlige tal. En tom liste repræsenteres af tallet 0. En liste med hovedet x og hale repræsenteret af ls kan repræsenteres af pairnums x ls. Så listen [1,3,5] i Miranda kan repræsenteres af

pairnums 1 (pairnums 3 (pairnums 5 0)).

spørgsmål a

Man kunne i stedet have forsøgt at repræsentere lister af naturlige tal i PCP v.h.a. <, >, Proj_{1} og Proj_{2} og lade Proj_{1} ls indeholde længden af listen ls. For eksempel skulle listen [1,3,5] så repræsenteres af < 3, < 1, < 3, 5 >>>. Hvorfor er dette ikke nogen god idé? (Vink: Ville der være problemer med at definere funktioner, der tager lister som argumenter?)

spørgsmål b

Nu skal vi se på funktionen map, der kendes fra Miranda:

map :: (* → **) → [*] → [**] map f ls = [f a | a <− ls]

Definer et udtryk F i PCF, så map kan laves som

map =^{def} fix_{(nat→nat)→nat→nat}F.

Funktionen map skal have den samme effekt på repræsentationer af lister (som beskrevet ovenfor), som map har på lister i Miranda.

spørgsmål c

Antag nu, at pairnums, projnum_{1} og projnum_{2} er defineret sådan, at projnum_{1} 7 reducerer til 3, og projnum_{2} 7 reducerer til 0. Brug left-most reductions (normal order reduction) på

map (λx : nat.x + x) 7

indtil en normalform nås. Medtag alle skridt.