UL/FRI/UNI-RI/TOR1/Izpiti/2006-11-09

Iz E-študij, proste zakladnice študentskega znanja

< UL | FRI | UNI-RI | TOR1 | Izpiti

Skoči na: navigacija, iskanje

Izpit z dne 09.11.2006
UL/FRI/UNI-RI/TOR1

Čas pisanja: 45 minut.
Literatura: -.

1. Naloga

Sestavite minimalni deterministični končni avtomat za jezik regularnega izraza ((0+01(0+00)*)*+1)*

(Napotek: deterministični končni avtomat lahko sestavite na pamet, brez postopka)

(20 točk)

Rešitev

če poenostavimo dobimo: (0+1)*

2. Naloga

Dokažite, da jezik

L = {

a 2 p

| p je prastevilo }

ni regularen.

(20 točk)

Rešitev

podobno kot na vajah za $a p$

3. Naloga

Dokažite, da jezik

L = {a i b i j c i d i j | i > = j > = 0}

ni kontekstno neodvisen.

(20 točk)

Rešitev

4. Naloga

Pretvorite gramatiko

$S \rightarrow AB | BA$

$A \rightarrow Aa | a$

$B \rightarrow bB | b$

v normalno obliko po Greibachovi.

(20 točk)

Rešitev

5. Naloga

Sestavite kontekstno neodvisno gramatiko za jezik

L = {

a n (b | b c) n a b *

| n>0}

in na kratko opišite pomen produkcij.

(20 točk)

Rešitev

$S \rightarrow AaB$

$A \rightarrow aAb | aAbc | ab | abc$

$B \rightarrow bB | epsilon$

Vzpostavljeno iz »http://www.e-studij.si/UL/FRI/UNI-RI/TOR1/Izpiti/2006-11-09«

Kategoriji: UL/FRI/UNI-RI/TOR1 | Izpiti

UL/FRI/UNI-RI/TOR1/Izpiti/2006-11-09

Iz E-študij, proste zakladnice študentskega znanja

1. Naloga

2. Naloga

3. Naloga

4. Naloga

5. Naloga

Osebna orodja

Imenski prostori

Različice

Pogled

Dejanja

Iskanje

navigacija

Tiskanje/izvoz

orodja