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.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; om du skriver med LaTeX, använd pdflatex för att göra om det till en pdf; Om du skriver i Word, välj spara som och välj filformatet pdf; inskannade handskrivna lösningar går också bra men LaTeX är bäst) senast Deadline. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske kort efter deadline 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 den har kommit upp. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus innan varje redovisning.

Uppdatering 2022-06-11: Bokningslistorna finns nu live här: https://www.csc.kth.se/cgi-bin/bokning/remores1.4/server/decoder?request:overview=yes&repository=progpomprov

Det är viktigt att du förbereder dig inför den muntliga redovisningen. Se till att ha bra koll på materialet som gås igenom i uppgifterna.

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ågot är oklart.

Generella regler för mästarprov såsom vad som krävs för godkänt finns på mästarprovssidan i Canvas.

Som exempel på hur kod-delen av en inlämningsuppgift kan se ut, se facit och rättningsmallar från Tentaarkivet i DD1361, till exempel 2017-09-18. Som exempel på hur en teorifråga kan besvaras, se facit och rättningsmallar från tentaarkivet i DD1362, till exempel från juni 2021.

Lycka till!

1. Nummerteckenspråk

Betrakta ett språk som bara består av nummertecken ("#", tokennamn Hash) separerade med nyrad (tokennamn Newline). 

Varje rad av nummertecken ingår i precis ett par av rader räknat från början av ett ord i språket, så t. ex. ingår den första raden i ett par med den andra raden, och den femte raden i ett par med den sjätte raden, osv.

För raderna x och y i varje par av rader gäller följande: om x har n stycken förekomster av Hash så har y antingen n stycken Hash eller n+1 stycken Hash eller n+2 stycken Hash.

Exempelsträng i språket:

#####
######
##
##

Definiera grafiskt en stackautomat (DPDA) som känner igen precis detta språk. Stackautomaten får bara ha övergångar som innehåller Hash, Newline eller tomma strängen (Epsilon). Märk tydligt ut starttillstånd och accepterande tillstånd i din DPDA.

2. Grammatikfunktion

Låt F vara en (beräkningsbar, matematisk) funktion som tar en grammatik G i en viss form och returnerar ett booleskt värde så att F(G) = true om och endast om det finns ett reguljärt uttryck som beskriver språket som definieras av G.

För varje möjligt värde för F(G), dvs. F(G) = true, F(G) = false, ange vad detta innebär för språket som definieras av G i förhållande till följande språkklasser, dvs. ange om språket tillhör klassen, språket inte tillhör klassen, eller om båda alternativen är möjliga:

A. Klassen av alla språk som kan parsas genom rekursiv medåkning.
B. Klassen av alla språk som känns igen av någon DFA.
C. Klassen av alla språk som känns igen av någon DPDA.

Motivera dina svar noggrant.

3. Minusaritmetik

Betrakta en grammatik som beskriver ett språk med minusuttryck över tal:

<Exp> ::= <Exp> Minus <Exp> | Num | LPar <Exp> RPar

Startsymbol: <Exp>

Tokens i språket:

- Minus: "-"
- Num: [0-9]+
- LPar: "("
- RPar: ")"

A. Definiera grafiskt en ändlig automat (DFA) som känner igen minusuttryck från språket som har flera olika härledningar i grammatiken. Din DFA får bara göra övergångar på tokens i språket. DFA:n behöver inte känna alla möjliga minusuttryck med flera härledningar, men den får inte vara begränsad till att känna igen minusuttryck som har ett visst förbestämt antal tokens. Märk tydligt ut starttillstånd och accepterande tillstånd i din DFA.

B. Ge ett exempel på ett minusuttryck som din DFA känner igen, både som sträng och tokensekvens, och ge två olika härledningar i grammatiken för uttryckets tokensekvens. Ange vilken ickeslutsymbol som väljs i varje härledningssteg, och gör det tydligt var dina två härledningar skiljer sig åt.

4. Utökningar av BNF

I olika utökningar av den grundläggande BNF-syntaxen för grammatiker används ofta Kleenestjärnan ("*"), frågetecknet ("?"), och plustecknet ("+") för att beskriva upprepningar av symboler, och hakparenteser ("[" och "]") för att ange omfånget för dessa operatorer. Kleenestjärnan betyder som vanligt noll eller flera förekomster, frågetecknet noll eller en förekomst, och plustecknet en eller flera förekomster.

A. För varje operator (*, ? och +), förklara kortfattat hur en grammatik som använder den operatorn kan konverteras till en grammatik som inte använder operatorn men beskriver samma språk.

B. Använd dina ansatser för att konvertera följande grammatik till en grammatik som inte använder operatorerna (och inte heller "[" eller "]") men som beskriver samma språk:

<Exp> ::= Var | <Exp> Lt <Exp>
<Stm> ::= Skip | Var Assign Num | If <Exp> Then <Stms> [ Else <Stms> ]? End
<Stms> ::= <Stm> [SemiColon <Stm>]*
<MethodDecl> ::= Ident LPar [ Var ]* RPar LBrack <Stms> RBrack
<ClassDecl> ::= Class Ident [ Extends [ Ident ]+ ]? LBrack [ <MethodDecl> ]+ RBrack

Startsymbol: <ClassDecl>

Tokens:

• Skip: "skip"
• SemiColon: ";"
• Var: [A-Za-z]+
• Assign: ":="
• Num: [0-9]+
• Ident: [A-Za-z]+
• If: "if"
• Then: "then"
• Else: "else"
• End: "end"
• Lt: "<"
• LPar: "("
• RPar: ")"
• LBrack: "{"
• RBrack: "}"
• Extends: "extends"
• Class: "class"

C. Ge en exempelsträng i språket som definieras av grammatikerna. Representera även strängen som en tokensekvens och ge en härledning i den nya grammatiken för den sekvensen från startsymbolen.

5. Komplementspråk

På matematisk nivå definierar vi språket L med hjälp av ordvariabeln w och tecknen a, b och c:

L = { wc | w är tom eller består av ett jämnt positivt antal a följt av ett jämnt positivt antal b }

Betrakta nu komplementspråket till L, dvs. mängden av alla ord som inte finns i L, över alfabetet med tecknen a, b och c. Ingår detta komplementspråk till L i klassen av alla reguljära språk? Motivera ditt svar noggrant.