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.

SVAR: BNF-grammatik med startsymbol <R> och slutsymboldefinitioner:

<R> ::= <Term> <TermList>
<TermList> ::= CONCAT <Term> <TermList> | ’’
<Term> ::= <Factor> <FactorList>
<FactorList> ::= UNION <Factor> <FactorList> | ’’
<Factor> ::= A | B | C | D | E | F | VOID | EPS | LPAR <R> RPAR | STAR LBR <R> RBR

CONCAT: "&"
UNION: "+"
A: "a"
B: "b"
C: "c"
D: "d"
E: "e"
F: "f"
VOID: "%"
EPS: "@"
LPAR: "("
RPAR: ")"
STAR: "*"
LBR: "{"
RBR: "}"

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.

SVAR: Vi representerar följande abstrakta reguljära uttryck som en sträng i språket: (ab)(c*|d*)

Sträng som lista av slutsymboler/tokens: LPAR A CONCAT B RPAR CONCAT LPAR STAR LBR C RBR UNION STAR LBR D RBR RPAR

Sträng efter insättning av tokendefinitioner: "(a&b)&(*{c}+*{d})"

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

Kontrolluppgift som lämnas som övning.

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.

Kontrolluppgift som lämnas som övning. Prioritetslager i grammatiken gör att den inte är tvetydig.

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}.

SVAR: {cb, ϵ}

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

SVAR: b(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)

SVAR: (d(ed)*ef)|f)

SVAR: (de)*f

Dessa två möjliga svar är ekvivalenta reguljära uttryck (beskriver samma språk).

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

SVAR: ∅ (reguljära uttrycket för tomma mängden)

d 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).

SVAR: ∅ (reguljära uttrycket för tomma mängden)

d 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).

SVAR: Om x = y så ε (reguljära uttrycket för mängden med bara tomma strängen), annars om x != y så ∅ (reguljära uttrycket för tomma mängden)

d 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.

SVAR: (rx1|rx2)

d 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.

SVAR: rx(r0)*

Vi tar först residualen av det språket som blev repeterat med Kleenestjärna och slår ihop det med L. Då fångas alla repetitioner i residualspråket som kommer efter förekomster av residualen av språket som blev repeterat.

d 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.

SVAR: Om eps(r1) returnerar sant så ((rx1 r2)|rx2), annars om eps(r1) returnerar falskt så rx1 r2 .

Fallen måste särskiljas eftersom det går att skippa r1-delen när ϵ ingår i språket, vilket gör att vi hamnar direkt i r2-delen av L och måste ta residualen av den delen. Om ϵ inte ingår i språket så behöver vi bara ta residualen av r1-delen av L.

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.

SVAR: {a,b}

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.

SVAR: Språket hk(L1, L2) tillhör klassen av alla reguljära språk.

För att se varför, låt d1 = (Q1, Σ, δ1, q1, F1) vara DFA:n som känner igen språket L1 (existerar ty L1 reguljärt). Konstruera nu DFA:n d = (Q1, Σ, δ1, q1, F), där F är mängden av alla tillstånd q i Q1 sådana att DFA:n (Q1, Σ, δ1, q, F1) accepterar något ord i L2. Vi kan alltid hitta alla dessa q eftersom L2 är reguljärt. DFA:n d känner igen hk(L1, L2), vilket etablerar att språket är reguljärt. Notera att enda (möjliga) skillnaden mellan d1 och d är mängden av accepterande tillstånd.