Ommästarprov Syntax

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Inlämningarna plagiatgranskas. Nytt för 2023 är att det inte är tillåtet att använda verktyg baserade på AI/maskininlärning i arbetet med lösningarna. Exempel på förbjudna verktyg är GitHub Copilot och ChatGPT.

Skriftliga lösningar som pdf-fil ska lämnas in i Canvas.

Det bästa är att använda LaTeX för att skapa texten. De flesta som använder LaTeX gör det via ett webbgränssnitt som till exempel Overleaf Links to an external site.. Om du bygger lokalt, tänk på att använda pdflatex så att resultatet blir en pdf-fil. Assistenterna ska inte behöva bygga LaTeXfiler själva och framför allt inte installera externa bibliotek. Det näst bästa är att använda Markdown Links to an external site. som är enklare än LaTeX och ger nästan lika bra resultat vid export till pdf. Resterande: Om ni använder Microsoft Word eller liknande - tänk på att spara som pdf så att alla kan läsa texten som det är tänkt utan att ha Word installerat.

Krav på lösningar:

Skriv ditt namn och KTH-mailadress överst på framsidan av inlämnad pdf. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline i Zoom, eller på plats för någon i lärarlaget. Tidsbokningen kommer att komma upp nära uppgiftens deadline och det kommer att anslås på Canvas när de har kommit upp. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus mellan varje par av redovisningar.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera dina lösningar.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om någon formulering är oklar.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas. Tänk på att mästarprovet bedöms efter sin sämst lösta uppgift så överarbeta inte enskilda uppgifter förrän alla andra är OK.

För inspiration till hur lösningar kan se ut, se lösningsförslag för syntaxdelar i facit och rättningsmallar från Tentaarkivet i DD1361. Det finns också referenslösningar för gamla syntaxmästarprov länkade i kursöversikten, men tänk på att dessa inte innehåller motiveringar som behövs i en inlämnad lösning!

1. Satsformler

Betrakta ett språk av satsformler, definierat enligt nedan:

- en eller flera stora bokstäver efter varandra ("A" till "Z") är en formel
- "0" är en formel
- "1" är en formel
- om X är en formel, så är detta en formel: "(" följt av X följt av ")"
- om X och Y är formler, så är detta en formel: X följt av "&" följt av Y
- om X och Y är formler, så är detta en formel: X följt av "#" följt av Y
- om X är en formel, så är detta en formel: "~" följt av X

a) Definiera tokens för satsformelspråket med hjälp av reguljära uttryck - högst 10 stycken tokens. Bortse från blanktecken som nyrad och blanksteg, och använd inte blanktecken i tokendefinitionerna.

b) Använd dina tokens från a) som slutsymboler i en BNF-grammatik som beskriver formelspråket. Din grammatik måste gå att använda som grund för en parser för formelspråket baserad på rekursiv medåkning och får inte tillåta mer än ett syntaxträd för någon sträng i språket. Märk tydligt ut startsymbolen i din grammatik.

c) Ge en härledning i din grammatik från b) för följande sträng, och illustrera sedan härledningen med motsvarande syntaxträd. Motivera kort varför strängen inte kan ha flera olika syntaxträd i din grammatik.

A & 1 & ~B # (~D # 0)

2. Operatoralternering

Betrakta ett språk av temporalformler, definierat enligt nedan:

- en eller flera stora bokstäver efter varandra ("A" till "Z") är en formel
- en eller flera små bokstäver efter varandra ("a" till "z") är en formel
- om X och Y är formler, så är detta en formel: X följt av "&" följt av Y
- om X är en formel, så är detta en formel: "μ" (lilla grekiska mu Links to an external site.) följt av en eller flera små bokstäver ("a" till "z") följt av "(" följt av X följt av ")"
- om X är en formel, så är detta en formel: "ν" (lilla grekiska nu Links to an external site.) följt av en eller flera små bokstäver ("a" till "z") följt av "(" följt av X följt av ")"

a) Definiera tokens för formelspråket med hjälp av reguljära uttryck - högst 10 stycken tokens. Bortse från blanktecken som nyrad och blanksteg, och använd inte blanktecken i tokendefinitionerna.

b) Definiera grafiskt en DPDA som känner igen delspråket av temporalformelspråket där:

- endast instanser av en av operatorerna "μ" och "ν" förekommer på varje parentesnästlingsnivå, och
- förekomsten av "μ" eller "ν" alterneras mellan parentesnästlingsnivåerna.

Stackautomatens övergångar får bara innehålla tokens från a) och tomma strängen (epsilon), dvs blanktecken bortses från och ska inte ingå i tokendefinitionerna. Stackautomaten får inte får ha några begränsningar gällande antalet parentesnästlingsnivåer.

Ledning: din DPDA måste till exempel se till att om "μ" förekommer (en eller flera gånger) på den tredje parentesnästlingsnivån i en sträng så förekommer endast "ν" (en eller flera gånger) på den fjärde parentesnästlingsnivån - om den nivån innehåller någon operator överhuvudtaget.

c) Förklara kortfattat varför följande sträng accepteras av din DPDA:

μ y (ν x (A) & ν z (z))

d) Förklara kortfattat varför följande sträng inte accepteras av din DPDA:

ν x (A & ν y (B))

3. Grammatikkomplement

Betrakta språket L över alfabetet {a,b,c,d,e,f,g} som definieras av följande BNF-grammatik med startsymbolen <X>:

<X> ::= <X> <Y> 'c' | <X> <Z> 'd' | 'b'
<Y> ::= <Y1> 'e' <Y> | ''
<Y1> ::= 'f' | 'g'
<Z> ::= <Z> 'a' | 'e'

Definiera grafiskt en DFA som känner igen komplementspråket till L, dvs mängden av alla strängar över det givna alfabetet som inte finns i L.

4. Okänt talspråk

Vi betraktar språk över alfabetet {p,q,r}. Givet ett tecken t i alfabetet och ett icke-negativt heltal j så menar vi med t^j strängen som består av precis j förekomster av t.

Låt nu k vara ett okänt men fixt positivt heltal i följande språkdefinitioner:

L1 = { p^n q^n | n <= k }

L2 = { p^n q^k | n > k }

L3 = { p^k q^n | k > n }

L4 = { p^n q^n r^n | n <= k }

L5 = { p^n q^n r^n | n >= k }

För vart och ett av språken L1, L2, L3, L4 och L5, ange om det går att parsa det med rekursiv medåkning. Motivera dina svar noggrant.