1. Wyznaczyć język generowany przez podaną gramatykę
   
   - reguły (te znaczki po prawej od strzałki) podpisać od 1 do ileśtam zaczynając od pierwszej.
   - zaczynamy od symbolu początkowego np. S
   
   S -->
   
   I podpisujemy nad strzałką z której reguł/reguły korzystamy po prostu podstawiając.
   Rekurencja jest kiedy symbol z lewej strony powtarza się z prawej strony i wstawiamy tą regułę priorytetowo(jako pierwszą) podpisując nad strzałką numer reguły z * np 1*. Przykłady rekurencji to: X-->XA, X-->AX
   Po podstawieniu rekurencji symbol stojący z prawej strony dajemy do wymyślonej potęgi. W tym przypadku XA^n lub A^n X
   Zwykłe reguły można wstawiać hurtem wpisując nad strzałką ich numery np. 1,2,3 i zapisuje się je w wyrażeniu w nawiasie ze znakiem + który oznacza w JAO "albo". Np. (<reg1> + <reg2> + <reg3>).
   Ważne aby się trzymać poziomu. Jak S ma reguły 1, 2, 3 to w hurcie nie podstawiamy tez reguły 4 która jest gdzie indziej.
   
   Gdy nam wyjdzie wyrażenie (y^k)*y lub y*(y^k) to trzeba to skrócić w ten sposób: y^(k+1) lub y^k gdzie k=1,2,3....
   ZAWSZE(!) jak są jakieś potęgi to trzeba podpisać n=0,1,2,3...; k=1,2,3 itd.
   
   - Zadanie jest dobrze zrobione i nie pochrzaniliśmy kolejności to wyjdą na końcu same małe literki
   
   2. Przekształcić daną gramatykę na gramatykę bez reguł zerowych
   
   - reguły zerowe to lambdy. Każdą lambdę trzeba oddzielnie usuwać nie usuwając innych.
   - reguły bezużyteczne to takie do których nie ma dojścia. Np. Jest symbol X z lewej strony a nie pojawia się nigdzie z prawej to się to skreśla Przy każdym przekształceniu warto popatrzeć czy nie występują.
   
   *Podstawianie działa na zasadzie:
   
   Podstawiamy A-->lambda
   
   do B--> AB|AC
   
   To wyjdzie nam coś takiego: B--> AB|AC|B|C
   
   Bo pierwsze się przepisuje a potem się wstawia.
   
   Jak już się wszystko "przemieli" to mamy gotowe zadanko.
   
   3. Przekształcić daną gramatykę do postaci monotonicznej (sprawdzić czy jest gramatyka bezużyteczna).
   
   - Tak jak w zagadnieniu nr. 2 (pozbywanie się lambd i wywalanie bezużytecznych reguł)
   - Mają być przynajmniej 2 znaki po prawej stronie
   - Można (a nawet trzeba) podstawiać np. B-->1 ponieważ tak jest łatwo pozbyć się pojedynczych znaków
   
   4. Przekształcić do postaci Chomskiego
    
      Chomsky - po prawej stronie 2 symbole duże (np. XX) lub 1 mały symbol (np. y)
   
   - Aby tak zrobić trzeba utworzyć nowe reguły np mamy taki przykład:
   
   S--> Xb|a
   X--> cY|WW
   
   robimy:
   
   S-->Xb zastąp S-->XB; B-->b
   X-->cY zastąp X-->CY; C-->c
   
   i koniec zadanka:
   
   S-->XB|a
   X-->CY|WW
   B-->b
   C-->c
   
   Ważne aby nie powielać reguł np. gdy B-->b to nie tworzyć potem D-->b.
   
   5. Przekształcić do postaci Greibach
   
   - Pozbyć się rekurencji, gdzie rekurencją jest A-->AB, a nie A-->BA (rekurencja jest kiedy symbol stoi na pierwszym miejscu)
   - Zawsze sprawdzać czy nie ma reguł zerowych czy bezużytecznych.
   - Rozwiązać tak aby mały symbol stał wszędzie na początku z prawej strony np. S-->aF|b|cDDD
   
   Mamy przykład: S-->SB|AB|BC
   
   Zaczynamy od Lematu 2 (pozbywanie się rekurencji)
   S-->SB
   
   alfa - symbol(e) przy znaku rekurencji
   beta - pozostałe reguły produkcji w regule produkcji
   
   Czyli w tym przykładzie:
   alfa = B
   beta1 = AB
   beta2 = BC
   
   Tworzymy nową regułę produkcji z wymyślonym znakiem. Po jej prawej stronie ma być: alfa|alfa_i_nasz_nowy_wymyślony_znak
   
   kontynuując przykład tworzymy:
   G-->B|BG
   
   Teraz wypieprzamy na chama rekurencję SB z reguły produkcji S. Ciach
   Dodajemy symbol G tam gdzie wywaliliśmy rekurencję.
   
   Czyli z tego: S-->SB|AB|BC
   Wychodzi to: S-->AB|BC|ABG|BCG
   
   i na koniec tych działań mamy tak:
   
   G-->B|BG
   S-->S-->AB|BC|ABG|BCG
   
   I teraz:
   
   Lemat 1 (podstawianie aby były małe symbole na początku)
   
   Podstawiamy co się da, wywalamy bezużyteczne i koniec zadanka.
   
   6.Wyznaczyć język bezkontekstowy będący konkatencją, sumą lub domknięciem Kleeniego.
   
   - suma – dodać wszystko z L1 i L2 (L1+L2)
   - konkatencja – pomnożyć każdy z każdym (L1*L2)
   - domknięcie Kleeniego – na przykładzie L2 leci się ze składnikami do potęg od 0 do iluśtam
    np. L2= {a,cb}
    to L2*= {lambda, a, cb, aa, acb, cba, cbcb....
   
   9. Podać wzory opisujące elementy tablicy C-Y-K
   
   - ponumerować dobrze tablicę C-Y-K z V (w prawo rosną dziesiątki, w dół jedności)
   - przepisać cały zapis:
   V<adres szukanego>={X|X → YZ;
   - napisać po średniku V x V w postaci np.
         („e” to należy do)   YeV11, ZeV24 } i podać tutaj k= <liczba jednostek przy pierwszym V>
   
   np. rozwiązaniem dla V12 jest
   
   V12={X|X-->YZ; YeV11, ZeV21} k=1
   
   Przykład dla V15:
   
   V15={X|X->YZ;YeV11, ZeV24} k=1
                                YeV12,ZeV33} k=2
                                YeV13, ZeV42} k=3
                                YeV14,ZeV51} k=4
   
   Wyznacza się to wszystko metodą V i koniec (ciach bach to z tym, to z tym i koniec zadania).
   
   10. Wykorzystując algorytm C-Y-K sprawdzić czy podane słowo należy do gramatyki.
   
   - narysować tabelę C-Y-K
   - w rogach uzupełnić znakami słowa pierwsze górne kratki
   - obczaić w regułach co produkują dane znaki
   - wypełnic pierwsze górne kratki po kolei tymi regułami
   - zrobić metodą V
   - na końcu (tj. V15) ma wyjść symbol początkowy. Jeżeli nie to słowo nie należy.
   
   12. Przekształcić daną gramatykę regularną do postaci w której symbol początkowy nie występuje po prawej stronie reguł produkcji. (thx to Smuga)
   
   to jest to co masz produkcje, rysujesz wykres, po czym dorabiasz kolejny węzeł który produkuje TO SAMO co początkowy i wszystkie węzły które wskazywały na początkowy przerzucamy na niego?
   typu:
   S -> aA | bB
   A -> aA | sS
   B-> bB | sS
   
   to dorabiamy węzeł K i zamieniamy tak:
   K -> aA | bB
   S -> aA | bB
   A -> aA | sK
   B-> bB | sK
   
   13. Przekształcić podaną gramatykę do postaci deterministycznej
   
   
   
   14. Przekształcić podaną gramatykę do postaci zupełnej
   
   Tak jak wyżej (pkt 13.) plus:
   
   
   
   16. Ocenić czy podany język (gramatyka) jest regularny, bezkontekstowy, kontekstowy, rekurencyjnie przeliczalny
   
   a) Gramatyka regularna - Jest jak po prawej stronie jest jak po prawej stronie jedna mała litera poprzedza jedną dużą (np. aB) lub występuję tylko jedna mała litera (np. a), a po lewej stronie występuje jeden duży symbol (np. A->)
   
   Przykład:
   
   S --> aB|aC|bS
   B --> a|aB
   C --> b
   
   b) Gramatyka bezkontekstowa - Jest jak po lewej stronie występuje jeden duży symbol (np. A -->), a po prawej jest wszystko jedno
   
   Przykład:
   
   S --> SBA|a|Lambda
   A --> aA|B|a
   B --> b
   
   c) Gramatyka kontekstowa - po lewej wszystko jedno i po prawej wszystko jedno. UWAGA - Ilość znaków po lewej musi być mniejsza lub równa, pojedynczym wyrażeniom z prawej.
   
   Przykład:
   
   SA --> ABC|aa|AA
   A --> CC|c
   BA --> BGA
   
   d) Rekurencyjnie przeliczalna - występuje kiedy jest jedna z powyższych. NIE JEST rekurencyjnie przeliczalna kiedy lambda jest po lewej stronie.
   
   Przykład (kiedy NIE JEST):
   
   Lambda --> BC|CD
   A --> a|AB
   
   
   ------------
   
   Podsumowując: Jeżeli jest punktem a) to jest także punktem b), c) i d). Jeżeli nie jest punktem  a) i b) ale jest c) to jest także punktem d). Jeżeli nie jest rekurencyjnie przeliczalna to nie jest niczym. Mam nadzieję, że to czujecie.
   
   17. Ocenić jak liczny jest dany język
   
   
   
   18. Napisać układ równań dla danego automatu Moore'a i rozwiązać go ze względu na dane Txy
   
   
   
   19. Dla automatu Meal'ego podanego w formie tabeli narysować graf automatu.
   
   
   
   20. Napisać układ równań dla danego automatu Mealy'ego i rozwiązać go ze względu na dane Rxy
   
   
   
   21. Dla danego automatu Moore'a napisać równoważny mu automat Mealiego (thx to Smuga)
   
   jak masz przykład z wykładu:
   
   Moore
   
   stan  |  0  |   1   | WY
      L    |  S  |   U   |  K
      U   |  U   |  L    |  A
      S   |  L   |   U   |  T
   
   tutaj przejście na Mealego jest proste. po prostu w miejsca liter S,U,L dopisujesz /to_co_litera_ma_na_wyjściu
   np:  S ma na wyjściu T,więc w każde S dopisujesz /T
   robisz tak dla wszystkich liter i na końcu usuwasz kolumnę WY. wychodzi Ci:
   
   Mealy
   
   stan  |  0  |   1 
      L    |  S/T  |   U/A 
      U   |  U/A   |  L/K
      S   |  L/K   |   U/A
   
   22. Dla danego automatu Meal'ego napisać równoważny mu automat Moore'a (thx to Smuga)
   
   gorzej wygląda w drugą stronę, ponieważ jeśli masz np. S/T i S/K  to traktujesz je jako inne węzły i trzeba wszystkie rozpisać. pokaże na drugim przykładzie z forum:
   to /x jest tym co znajdzie się potem w kolumnie WY.
   
   Mealy
   
   stan  |  0     |   1 
      A    |  C/Z  |  B/Y
      B    |  B/Z  |  A/X
      C    |  A/Z  |  B/X
   
   mamy tutaj i B/X i B/Y, trzeba więc wypisać je wszystkie. w kolumny 0 i 1 wpisujemy dla wszystkich wariantów A,B,C i to mamy w tabeli powyżej.
   
   stan     |    0    |   1     |  WY
     A/Z    |  C/Z  |  B/Y   |   Z   <=== to samo na WY co po /
     A/X    |  C/Z  |  B/Y   |   X   <=== te same produkcje co w tabeli wyżej
      B/X    |  B/Z  |  A/X   |   X
      B/Y    |  B/Z  |  A/X   |   Y
      B/Z    |  B/Z  |  A/X   |   Z
      C/Z    |  A/Z  |  B/X   |   Z
   
   teraz trzeba każdy kolejny wariant zapisać pod inną literą:
   
   stan  |  0 |  1   |  WY
      E    |  J  |  H   |   Z   
      F    |  J  |  H   |   X   
      G    |  I  |  F   |   X
      H    |  I  |  F   |   Y
      I     |  I  |  F   |   Z
      J     |  E  |  G  |   Z
   
   23. Pokazać, czy dane wyrażenie jest akceptowalne przez automat ze stosem. (thx to Bugi89)
   
   Masz jakąś taśmę np:
   A B B B A LAMBDA
   
   Stan wewnętrzny automatu np:
   q0
   
   I stos:
   #
   
   Bierzesz pierwszy symbol z taśmy (A) stan wewnętrzny automatu (q0) i ostatni symbol ze stosu (#).
   //Jak bierzemy symbol ze stosu to jest on kasowany, oprócz #
   Składasz to w takie coś: (A, q0, #).
   Teraz szukasz w funkcjach przejścia po lewej stronie tego co Ci wyszło czyli (A, q0, #).
   Powiedzmy, że znalazłeś takie coś (A, q0, #) -> (q1, B).
   To w nawiasie po prawej znaczy: stan wewnętrzny automatu zamieniamy na q1 i do stosu dopisujemy B.
   
   Teraz masz taką taśmę:
   A B B B A LAMBDA
   
   Stan wewnętrzny automatu:
   q1
   
   I stos:
   #B
   
   Bierzesz drugi symbol z taśmy (B) stan wewnętrzny automatu (q1) i ostatni symbol ze stosu (B).
   //Jak bierzemy symbol ze stosu to jest on kasowany, oprócz #
   Składasz to w takie coś: (B, q1, B).
   Teraz szukasz w funkcjach przejścia po lewej stronie tego co Ci wyszło czyli (B, q1, B).
   Powiedzmy, że znalazłeś takie coś (B, q1, B) -> (q0, BB).
   To w nawiasie po prawej znaczy: stan wewnętrzny automatu zamieniamy na q0 i do stosu dopisujemy BB.
   
   Teraz masz taką taśmę:
   A B B B A LAMBDA
   
   Stan wewnętrzny automatu:
   q0
   
   I stos:
   #BB
   
   Bierzesz trzeci...

TO NIE JEST PEWNE :

VS

1. do postaci monotonicznej
S->AB|ASA|DC|Lambda
A->CA|0
B->1C|1
C->CA|CC
D->DA|1

O ile dobrze pamiętam lambda prodkcji ta reguła >1 nie dotyczy.

S->AB|ASA|DC|lambda
A->CA|0E
B->1C|1E
C->CA|CC
D->DA|1E
E->lambda

Cytat: Vandervir w 2011-01-28, 11:42:33

2. Hierarchia Chomskiego

• Typ 0: Języki rekurencyjnie przeliczalne:
  Wszystkie produkcje, byleby nie było lambdy po lewej stronie

• Typ 1: Języki kontekstowe:
  Długość lewej strony <= od długość prawej strony produkcji no i mają kontekst, choć nie muszą mieć. Ponieważ kontekstowe są też rek.przeliczalne, wciąż lambdy po lewej nie może być)

• Typ 2: Języki bezkontekstowe:
  Tak jak wyżej, tylko brak kontekstu.

• Typ 3: Języki regularne:
  Takie które zawierają jedynie produkcje typu:
  S->x
  S->xA

Cytat: Vandervir w 2011-01-28, 11:42:33

3. L =|a*b*c| wyznaczyc produkcje i narysowac graf

S->aA|bB|cC|
A->aA|bB|cC
B->bB|cC
c->lambda

Cytat: Vandervir w 2011-01-28, 11:42:33

4. do postaci greibach
A->BA|Aa|AB|a
B->BA|BB|b

Poprawione i scalone tutaj rozwiązanie:

Kod: [Zaznacz]

A->BA|Aa|AB|a
       L  L
B->BA|BB|b
    L  L

A->BA|a|BAC|aC
   ^    ^
B->b|bD //OK
C->a|B|aC|BC
^    ^
D->A|B|AD|BD
     ^    ^

---


A->bA|bDA|a|bAC|bDAC|aC //OK
B->b|bD  //OK
C->a|b|bD|aC|bC|bDC  //OK
D->A|b|bD|AD|bD|bDD
   ^      ^
         
---

A->bA|bDA|a|bAC|bDAC|aC    //OK
B->b|bD                                 //OK
C->a|b|bD|aC|bC|bDC          //OK
D->bA|bDA|a|bAC|bDAC|aC|b|bD|bAD|bDAD|aD|bACD|bDACD|aCD|bD|bDD //OK

Cytat: Vandervir w 2011-01-28, 11:42:33

5. Graf moora i wyzznaczyc R31
   abc
1|212|X
2|213|Y
3|322|Z

R31=aR31 + bR21 + cR21
R21=aR21 + bR11 + cR31
R11=aR21 + bR11 + cR21 + lambda //note: moore przyjmuje lambdy na wejściu


R31=a*(b+c)R21  //wyłączyłem R21 (UWAGA! na przed czy po nawiasie z tym wyłączaniem)
R21=a*(bR11 + cR31) //wzór poniżej
R11= b*[(a+c)R21 + lambda] //wzór i wyłączenie R21

Jeśli X=AX + B to:

X= A*B (jeśli lambda *nie* należy do A)
X= A*(B + W) (jeśli lambda należy do A)

gdzie W jest dowolnym wyrażeniem regularnym



R31=a*(b+c)R21
R21=a*bR11 + a*cR31 //bo za chwilę podstawimy za R11
R11= b*(a+c)R21 + b*

R31=a*(b+c)R21
R21=a*b[b*(a+c)R21 + b*] + a*cR31

R31=a*(b+c)R21
R21=a*bb*(a+c)R21 + a*bb* + a*cR31

R31=a*(b+c)R21
R21=[a*bb*(a+c)]*(a*bb* + a*cR31) //ten Wzorek


R31=a*(b+c)R21
R21=[a*bb*(a+c)]*a*bb* + [a*bb*(a+c)]*a*cR31


R31=a*(b+c)[a*bb*(a+c)]*a*bb* + a*(b+c)[a*bb*(a+c)]*a*cR31

R31=[a*(b+c)[a*bb*(a+c)]*a*c]*a*(b+c)[a*bb*(a+c)]*a*bb*


Jeszcze raz przypominam, że nie odpowiadam za jakość tych rozwiązań, choć dołożyłem wszelkich starań, aby były dobre.