Poniżej umieszczam pytania z przykładowego egzaminu
wraz z rozwiązaniami, które były przedstawione na ostatnim
wykładzie z AUG. Jesli ktoś ma podobne materiały np. z
poprzednich lat to prosiłbym o podzielenie się nimi.

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
1. Uszereguj języki:

a) (zbiór pusty)
b ) {0,1}*
c) {e}
d) {w E {a,b}*: długosć "w" jest liczbą parzystą}
e) {10}*

--------------------------------------------------------------
Odp: a), c), e), d), b )

2. Dopasuj automaty skończone do wyrażeń:
(poniżej są tabelki z już przyporzadkowanymi wyrażeniami

a)
___|a|b
_>1|1|2 = a*bb*
__f2|_|2

b )
___|a|b
>f1|1|2 = (aub)*
_ f2|1|2

c)
___|a|b
>f1|1|2 = a*b*
_f2|_ |2

d)
___|a|b
>f1|2|2 = e
__2|2|2

e)
___|a|b
>f1|2|2 = ((aub)(aub))*
__2|1|1

3.Gramatyki

- czy następująca gramatyka jest jednoznaczna?
S->aSb|bSa|e (TAK)
- czy w następujacej gramatyce można wyprowadzić
słowo puste? S->abS|Sba|aa (NIE)
- czy język gramatyki jest skończony?
S->abS|bSa|a (NIE)
- czy w gramatyce można wyprowadzić "abab"?
S->SabS|e (TAK)
- czy gramatyka generuje pusty język?
S->aSb|bSa|SS (TAK)

4.Języki

- Suma języków bezkontekstowych jest
bezkontekstowa. (TAK)
- Przecięcie języków regularnych jest językiem
regularnym. (TAK)
- Jeśli gramatyka jest jednoznaczna to każde
słowo, które można z niej wyprowadzić ma tylko
jedno drzewo wyprowadzeń. (TAK)
- Jeśli gramatyka jest jednoznaczna to każde
słowo, które mozna z niej wyprowadzić ma tylko
jedno wyprowadzenie. (NIE)
- Każdy język regularny jest
bezkontekstowy. (NIE)
- Dla każdego języka regularnego istnieje
rozpoznający go automat skończony. (TAK)

5.Żeby gramatyka była:

- (S)LR(1) to musi być jednoznaczna. (TAK)
- (S)LR(1) to musi zawierać jednostronną
rekursję. (NIE)
- LL(1) to musi się dać w niej wyprowadzić
słowo puste e. (NIE)
- LL(1) to należy ją poddać lewostronnej
faktoryzacji. (TAK)
- LL(1) to nie może zawierać lewostronnej
rekursji. (TAK)

6.W parserach:

- LL(1) komórki zawierają (prawe strony)
produkcji do rozwinięcia. (TAK)
- LL(1) zawartość stosu odpowiada temu, co ma
być jeszcze wczytane z wejścia. (TAK)
- LL(1) na stosie mogą znajdować się terminale
i nieterminale. (TAK)
- (S)LR(1) drzewo wyprowadzenia jest
konstruowane w kolejnosci prefiksowej. (NIE)
- LL(1) drzewo wyprowadzenia jest
konstruowane w kolejnosci prefiksowej. (TAK)






mam egzamin z zeszłego roku (niestety nie rozwiązany). Zebralem z niego oraz egzaimnu powyżej wczystkie pytania z zadań 5 i 6. (niektore były na obu). oto wszystkie mozliwe ptania jakie były, na 3 z nich nie jestem pewien odpwiedzi, macie może jakies pomysły? Cala reszta jest na 100% dobrze:

- LL(1) - gramatyka musi byc jednoznaczna
- LL(1) - nie może zawierać lewostronnej rekursji
- LL(1) - drzewo wyprowadzane jest PREfixowo
- LL(1) trzeba poddac faktoryzacji jesli prawe strony zaczynaja sie tak samo
- LL(1) to NIE musi się dać w niej wyprowadzić słowa pustego e
- LL(1) komórki zawierają (prawe strony) produkcji do rozwinięcia
- LL(1) zawartość stosu odpowiada temu, co mabyć jeszcze wczytane z wejścia.
- LL(1) na stosie mogą znajdować się terminale i nieterminale.


- (S)LR(1) - gramatyka musi byc jednoznaczna
- (S)LR(1) - drzewo wyprowadzane jest POSTfixowo
- (S)LR(1) - NIE należy poddawać lewostronej faktoryzacji,
- (S)LR(1) - NIE musi zawierać jednostronną rekursję.
- (S)LR(1) - komóki tablicy parsera ZAWIERAJĄ akcje shift i reduce
- (S)LR(1) - na stosie mogą znajdować się stany automatu, terminale i nieterminale. / wydaje mi sie ze stany automatu nie maja tu nic wspolnego
- (S)LR(1) - zawartość stosu odpowiada temu, co zostało wczytane z wejcia / NIE WIEM
- (S)LR(1) to MOŻE się dać w niej wyprowadzić słowo puste / nie jestem pewien