Mästarprov i Syntax

Mästarprovet i syntax 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. Det är 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, Google Gemini och ChatGPT.

Skriftliga lösningar på mästarprovet ska lämnas in som en enda pdf i Canvas. Skriv ditt namn och din KTH-epostadress överst på framsidan i din inlämnade skriftliga lösning. Inuti din lösning, märk tydligt ut vilken av de tre mästarprovsdelarna du svarar på, eftersom varje del bedöms enskilt.

Alla som lämnar in lösningar på mästarprov syntax har utrymme för ett mindre fel för vart och ett av de tre mästarprovsdelarna. Den som redovisat labb S1 innan deadline för bonus har utrymme för ytterligare ett mindre fel på mästarprovsdelen om automater och reguljära uttryck. Om antalet mindre fel är inom det tillåtna utrymmet på en mästarprovsdel så måste de rättas till under den muntliga redovisningen för att bli godkänd på den delen. Om en mästarprovsdel har fler mindre fel än de tillåtna eller något allvarligt fel innebär det att den delen i mästarprovet i syntax är underkänd. Mästarprovsdelar som godkänts både skriftligt och muntligt kan tillgodoräknas under mästarprov i syntax under detta och följande läsår. Till exempel kan du på ommästarprovet i syntax för årets kursomgång tillgodoräkna dig delen om automater och reguljära uttryck om motsvarande del godkändes på detta mästarprov.

Det bästa är att använda LaTeX för att skapa texten för den skriftliga lösningen. 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 LaTeX-filer själva och framför allt inte behöva installera externa bibliotek. Det näst bästa är att använda Markdown som är enklare än LaTeX och ger nästan lika bra resultat. Precis som med LaTeX behöver du konvertera din Markdown-lösning till en pdf innan du skickar in, t ex via verktyget pandoc Links to an external site.. 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.

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 finns i kurs-PM under examination -> mästarprov. Kurs-PM finns länkat från årets förstasida. Tänk på att du behöver bli godkänd på alla delar av mästarprovet i syntax för att kunna bli klar med mästarprovsdelen i kursen, så överarbeta inte en uppgift förrän du bedömer att du har rimliga lösningar på alla uppgifter.

Om du har lämnat in den skriftliga lösningen i tid så behöver du för att få godkänt även boka in dig på en muntlig redovisning. Muntliga redovisningstider kommer att anslås på Canvas i nära anslutning till mästarprovets deadline. 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. Den muntliga redovisningen tar 10 minuter för dig, men de som bedömer dig har 5 minuters paus mellan varje par av redovisningar.

1. Grammatiker

Låt R vara språket av reguljära uttryck över de små bokstäverna a, b, c, d, e, och f. R har följande egenskaper:

• Från strängar i R kan nya strängar i R konstrueras med hjälp av representationer av operatorerna union, konkatenering och slutning/repetition (Kleenestjärna).

• Union och konkatering utförs med infixnotation, så om s1 och s2 är strängar i R så kan union t ex vara strängarna "s1|s2" eller "s1+s2" (exakt hur operatorer representeras i R är inte förbestämt).

• Det finns en sträng i R som representerar det reguljära uttrycket (konstanten) för den tomma mängden ∅.

• Det finns en sträng i R som representerar det reguljära uttrycket (konstanten) för mängden som bara innehåller tomma strängen ε.

• Det finns strängar i R som representerar de reguljära uttrycken (konstanterna) för var och en av mängderna som bara innehåller en liten bokstav.

• Det går att använda parentespar för att gruppera delsträngar (deluttryck) i en sträng i R.

a.) Definiera en grammatik i BNF för R med de angivna egenskaperna som dessutom uppfyller följande krav:

• Startsymbolen för grammatiken är tydligt angiven.

• Grammatiken går att använda som grund för en parser konstruerad med rekursiv medåkning.

• Grammatiken är inte tvetydig.

b.) Låt L vara ett språk över alfabetet Σ = {a,b,c,d,e,f} definierat som

L = { abw | w innehåller antingen godtyckligt antal c eller godtyckligt antal d }.

Representera det reguljära uttrycket för L som en sträng s i R.

c.) Ge en härledning i din grammatik som visar att strängen s i b.) verkligen tillhör R.

d.) Ge ett syntaxträd för strängen s i b.) och argumentera kort varför det bara finns ett enda syntaxträd för s i din grammatik.

2. Automater och reguljära uttryck

Låt alfabetet Σ={a,b,c,d,e,f} och definiera för symbolen x i Σ och språket L över Σ residualspråket för L med avseende på x som

res(x,L) = { w | xw ingår i L }.

a.) Beskriv res(c,L) som en mängd av strängar för fallet då L = {ccb,c,bc}.

b.) Beskriv res(a,L) som ett reguljärt uttryck då L är språket som beskrivs av följande reguljära uttryck: (ab)*

c.) Beskriv res(e,L) som ett reguljärt uttryck då L är språket som beskrivs av följande reguljära uttryck: (ed)*(ef)

d.) Låt L vara ett reguljärt språk över Σ.

i.) Antag att L är tomma mängden ∅. Konstruera ett reguljärt uttryck som beskriver res(x,L).

ii.) Antag att L är mängden som bara består av tomma strängen ε. Konstruera ett reguljärt uttryck som beskriver res(x,L).

iii.) Antag att L är mängden som bara innehåller en symbol y från Σ. Konstruera ett reguljärt uttryck som beskriver res(x,L).

iv.) Antag att L beskrivs av ett reguljärt uttryck r som består av en union av två reguljära uttryck som beskriver språken L1 respektive L2. Antag också att rx1 och rx2 är de reguljära uttrycken som beskriver res(x,L1) respektive res(x,L2). Konstruera ett reguljärt uttryck som beskriver res(x,L) med hjälp av rx1 och rx2.

v.) Antag att L beskrivs av ett reguljärt uttryck r som består av en slutning/repetition (Kleenestjärna) av ett reguljärt uttryck r0 som beskriver språket L0. Antag också att rx är det reguljära uttrycket som beskriver res(x,L0). Konstruera ett reguljärt uttryck som beskriver res(x,L)
med hjälp av rx och r0. Motivera kort varför ditt svar är korrekt.

vi.) Antag att L beskrivs av ett reguljärt uttryck r som består av konkateneringen av två reguljära uttryck r1 och r2 som beskriver språken L1 respektive L2. Antag också att rx1 och rx2 är de reguljära uttrycken som beskriver res(x,L1) respektive res(x,L2). Konstruera ett reguljärt uttryck som beskriver res(x,L) med hjälp av r1, r2, rx1 och rx2. Motivera kort varför ditt svar är korrekt.

Ledning för vi.): du kan anta att det finns en funktion eps(r0) som för ett reguljärt uttryck r0 returnerar sant om den tomma strängen ε ingår i språket som r0 beskriver och falskt annars.

3. Språkklasser

Låt Σ vara ett alfabet och definiera språkoperatorn högerkvot (hk) som tar två språk L1 och L2 över Σ och returnerar ett nytt språk över Σ som

hk(L1,L2) = { w | det finns ett ord v så att v ingår i L2 och wv ingår i L1 }.

a.) För fallet Σ = {a,b}, L1 = {ba,aa,b} och L2 = {a}, ge en definition av språket hk(L1,L2) genom att lista alla dess strängar som en mängd.

b.) Låt L1 och L2 vara reguljära språk över alfabetet Σ. Vilken är den minsta språkklass som behandlats i kursen som hk(L1,L2) med säkerhet tillhör? Motivera svaret noggrant. 

Ledning för b.): använd det faktum att det finns en DFA som beskriver varje reguljärt språk och begrunda mängden av accepterande tillstånd.