To tylko jedna z 12 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
1. Wyznaczyd język generowany przez podaną gramatykę - reguły (te znaczki po prawej od strzałki) podpisad 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 wstawiad 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. ( + + ) . Ważne aby się trzymad 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ócid w ten sposób: y^(k+1) lub y^k gdzie k=1,2,3.... ZAWSZE(!) jak są jakieś potęgi to trzeba podpisad n=0,1,2,3... ; k=1,2,3 itd. - Zadanie jest dobrze zrobione i nie pochrzaniliśmy kolejności to wyjdą na koocu same małe literki 2. Przekształcid daną gramatykę na gramatykę bez reguł zerowych - reguły zerowe to lambdy. Każdą lambdę trzeba oddzielnie usuwad 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 popatrzed 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łcid daną gramatykę do postaci monotonicznej (sprawdzid czy jest gramatyka bezużyteczna). - Tak jak w zagadnieniu nr. 2 (pozbywanie się lambd i wywalanie bezużytecznych reguł) - Mają byd przynajmniej 2 znaki po prawej stronie - Można (a nawet trzeba) podstawiad np. B--1 ponieważ tak jest łatwo pozbyd się pojedynczych znaków 4. Przekształcid do postaci Chomskiego Chomsky - po prawej stronie 2 symbole duże (np. XX ) lub 1 mały symbol (np. y ) - Aby tak zrobid trzeba utworzyd 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
(…)
… 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…
…
-----------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. Ocenid jak liczny jest dany język
18. Napisad układ równao dla danego automatu Moore'a i rozwiązad go ze względu na dane Txy
19. Dla automatu Meal'ego podanego w formie tabeli narysowad graf automatu.
20. Napisad układ równao dla danego automatu Mealy'ego i rozwiązad go ze względu na dane Rxy
21. Dla danego automatu Moore'a napisad równoważny mu automat Mealiego (thx to Smuga)
jak masz przykład z wykładu:
Moore
stan | 0 | 1
L | S | U
U | U | L
S | L | U
| WY
| K
| A
| T
tutaj przejście na Mealego jest proste. po prostu w miejsca liter S,U,L dopisujesz…
... zobacz całą notatkę
Komentarze użytkowników (0)