Lessons

LEKTIONER

REKOMMENDERADE UPPGIFTER

KAPITEL

UPPGIFTER ATT REDOVISA

1

Test 1.1a),e),f)
Övn 1.1, Övn 1.2
Test 2.1a) - f)
Test 2.2b),c), Test 2.3a),b)

1.1-1.4,
2.1-2.3

Konstruera både reguljära uttryck och finita automater för
1. (i) L_i = {aⁿaⁿ | n tillhör {0,1,2,...}},
(ii) L_ii = {aⁿzaⁿ | n tillhör {0,1,2,...} och z tillhör {a,b}^*},
2. L_i:s komplementspråk, då komplementet tas med avseende på
(i) {a}^*, (ii) {a,b}^*.

2

Test 2.4a),b)
Test 2.5a),b),c)
Test 2.6a),b),c)

2.4-2.6

Konstruera både reguljära uttryck och finita automater för följande två språk. Beskriv eventuell förekomst av ickedeterminism i dina automater!
3.Språket över {a, b, c} vars strängar börjar på a och innehåller en eller flera förekomster av varje tecken.
4. Språket över {a,b} vars strängar har a som det tredje tecknet från slutet.

3

Test 2.7
Övn 2.3a), b)
Övn 2.5a), b), c)
Övn 2.6a), b)
Övn 2.7
Övn 2.8a) - f)
Övn 2.9a), b), c)
Övn 2.10, 2.12, 2.13, 2.14

2.4-2.8

5. Kör delmängdskonstruktionen på nedanstående NFA (så att en DFA erhålles)

6. Tillståndsminimera följande DFA

4

Test 2.8 d), e)
Test 3.1
Test 3.2a) -e)
Övn 3.1, 3.2, 3.4, 3.5

3.1, 3.2

Nedanför presenteras två språk. Red ut för vart och ett av dem, om det är reguljärt! Om du menar att det är det, konstruera en DFA eller ett reguljärt uttryck för språket. Annars, använd pumpning för att bevisa bristen på reguljäritet.
7. L₁={w över {a,b} | w innehåller lika många förekomster av aa som av bb},
8. L₂={w över {a,b} | w innehåller lika många förekomster av ab som av ba}.
ANM. Förekomster kan vara sammanflätade eller åtskilda. T.ex. som i strängen aaaa, där det finns tre sammanflätade förekomster av aa, men högst två åtskilda förekomster. Och i strängen aba saknas åtskilda förkomster av ab och ba, medan det finns en förekomst av vardera om vi tillåter dem att flätas samman. I de två uppgifterna räknar vi samtliga förekomster, även sammanflätade.

5

Test 3.3, Test 3.4
Övn 3.3, 3.7, 3.8, 3.9
Test 3.6a),b)
Övn 3.13c), d), e), Övn 3.14

3.3, 3.4

Konstruera CFG:er för nedanstående två språk:
9. L₂ (Se ovan.)
10. L₃ över {a,b} vars strängar har udda längd och egenskapen att mittersta tecknet överensstämmer med sista tecknet.

6

Test 4.1b)
Övn 4.1- 4.3
Test 4.2a), b)
Övn 4.4a), b), c)
Övn 4.7a), b), c), d)

3.6,
4.1-4.4

Sammanhangsfritt? Om JA, konstruera en PDA för språket. Om NEJ, bevisa bristen på sammanhangsfrihet med hjälp av pumpning.
11. Språket över {a, b} vars strängar är av typ xy där y är lika med x inverterad, dvs varje a i x är i y utbytt mot b, och varje b i x är i y utbytt mot a, t.ex. är baaabb en sådan sträng
12. Språket över {a, b} vars strängar är av typ xy där y är lika med x inverterad och reverserad, t.ex. är baabba en sådan sträng.

7

Test 7.1a), b)
Övn 7.1a),b),c),e),g)

7

Betrakta två godtyckliga Turingmaskiner M₁ och M₂. Vilka av nedanstående problem är (Turing)avgörbara?
13. Finns det någon sträng
(i) som M₁ accepterar?
(ii) som både M₁ och M₂ accepterar?
14. Finns det något ickeblankt tecken som både M₁ och M₂ skriver vid körning på blank tape?