Forum Informatyka UJ forum Strona Główna Informatyka UJ forum
Rocznik 2005 - czyli najlepsze forum w sieci
 
 FAQFAQ   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy   GalerieGalerie   RejestracjaRejestracja 
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Rodzaje gramatyk

 
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 1 semestr - Informatyka
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Śro 17:38, 01 Lut 2006    Temat postu: Rodzaje gramatyk

czy moglibyscie napisac w zrozumialy sposob podzial gramatyk? bo z wykladow nie moge nic wywnioskowac. co to znaczy ze jakas gramatyka jest taka a nie inna, jakie musi spelniac warunki aby taka byc...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Fidel
żul



Dołączył: 19 Lis 2005
Posty: 649
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Śro 17:49, 01 Lut 2006    Temat postu:

no ja mam ten sam problem :P

ale troche nizej jest jakis drugi sposob dekodowania moze prostrzy - nie mialem jeszcze czasu na to patrzec - jakies powiazania z maszyna Turinga
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Śro 17:55, 01 Lut 2006    Temat postu:

Klasa 0 - żadnych ograniczeń, dowolne mieszaniny terminali i nieterminali mogą przechodzić w dowolne mieszaniny terminali i nieterminali.
Klasa 1 - gramatyki kontekstowe - żadna produkcja nie skraca długości słowa. Czyli z AA nie może się zrobić A, ale aA albo ac tak.
Klasa 2 - gramatyki bezkontekstowe - to co w klasie 1 + po lewej stronie produkcji mamy jedynie jeden nieterminal. Czyli są one postaci A -> AAA, B -> bcAAB, B -> c.
Klasa 3 - gramatyki regularne (prawo albo lewostronne) - to co w klasie 2 + wszystkie produkcje są postaci A -> b lub A -> Bb (przykład lewostronnej). Czyli z każdego nieterminala wychodzi albo jeden terminal, albo jeden nieterminal + jeden terminal.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Śro 17:59, 01 Lut 2006    Temat postu:

a jak to wy glada ze slowami pustymi? gdzie moga sie pojawiac a gdzie nie?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Śro 18:05, 01 Lut 2006    Temat postu:

Słów pustych nie może być po lewej stronie produkcji w żadnej gramatyce, ani po prawej w gramatyce regularnej. Czyli nigdy nie można tworzyć czegoś z niczego, a w regularnej nie można zamieniać nieterminali na puste, zawsze musi być dokładnie jeden terminal + ewentualnie jeden nieterminal.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
ostoj
Przewijak Tasmy



Dołączył: 08 Lis 2005
Posty: 883
Przeczytał: 0 tematów

Skąd: Tychy

PostWysłany: Śro 18:13, 01 Lut 2006    Temat postu:

dzieki Madras
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Śro 19:48, 01 Lut 2006    Temat postu:

Pozwole sobie na pewna polemike ;P

Madras napisał:
Klasa 0 - żadnych ograniczeń, dowolne mieszaniny terminali i nieterminali mogą przechodzić w dowolne mieszaniny terminali i nieterminali.


Tu sie jeszcze zgodze, ale, tak jak zaznaczyles w drugim poscie, nie moze byc po lewej slowa pustego. A tak to wolna amerykanka :)

Madras napisał:

Klasa 1 - gramatyki kontekstowe - żadna produkcja nie skraca długości słowa. Czyli z AA nie może się zrobić A, ale aA albo ac tak.


To jest oczywiscie podklasa klasy 0. Jedna bardzo wazna rzecz, ktorej nie napisales - slowa pustego nie moze byc po prawej stronie (bo wtedy skracalaby sie dlugosc slowa)

Madras napisał:
Klasa 2 - gramatyki bezkontekstowe - to co w klasie 1 + po lewej stronie produkcji mamy jedynie jeden nieterminal. Czyli są one postaci A -> AAA, B -> bcAAB, B -> c.


No i tutaj zaczyna sie polemika :) Gramatyki klasy 2 NIE SA podklasa gramatyk klasy 1 gdzyz tutaj slowo puste MOZE wystepowac po prawej stronie. Natomiast jesli wezmiemy klase 2 bez jezykow zawierajacych slowo puste (czyli de facto takich, w ktorych wystepuje produkcja: nieterminal -> slowo puste) to to juz bedzie podklasa klasy 1.


Madras napisał:
Klasa 3 - gramatyki regularne (prawo albo lewostronne) - to co w klasie 2 + wszystkie produkcje są postaci A -> b lub A -> Bb (przykład lewostronnej). Czyli z każdego nieterminala wychodzi albo jeden terminal, albo jeden nieterminal + jeden terminal.


Tutaj male sprostowanie: ilosc nieterminali po prawej moze byc dowolna, pod warunkiem oczywiscie, ze "przyrastaja" z jedej strony nieterminala.
Czyli moga byc produkcje typu:
A -> abcd
A -> Baaba (A-> aabaB dla prawostronnie regularnych)

I tutaj juz nie ma zadnych obostrzen: klasa 3 pieknie zawiera sie w klasie 2, a nawet w klasie 1 (bo slowo puste nie moze byc po prawej stronie zadnej produkcji).



Ufff, to chyba tyle. Jakby byly jeszcze jakies pytania czy watpliwosci to dawac - a nuz znam odpowiedz :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Śro 20:04, 01 Lut 2006    Temat postu:

Cytat:
A -> abcd

Widzisz, też tak uważałem do ostatniego kolokwium z WdI, ale ćwiczeniowiec uświadomił mnie, że się mylę. Tylko jeden terminal. Z wykładu:
Cytat:
gramatyki regularne: produkcje mają postać (gramatyki lewostronnie regularne):
A -> Bb

A z tymi słowami pustymi to się zaraz upewnię i napiszę ;].


Ostatnio zmieniony przez Madras dnia Śro 20:44, 01 Lut 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Śro 20:14, 01 Lut 2006    Temat postu:

Dalej sie bede polemizowal :P

dr Maciej Slusarek napisał:
Klasa 3 ­– gramatyki regularne: produkcje mają postać (gramatyki lewostronnie regularne):
A -> Bb, gdzie A e N, B e N u {e}, b e T* , b <> e
Analogicznie: prawostronnie regularne: produkcje postaci A à bB.
Przykład języka regularnego: L (G_10)


Tam jest b nalezy do T* i b rozne od slowa pustego. To znaczy ze b moze byc dowolnym niepustym ciagiem nieterminali.


A to co mowia cwiczeniowcy czasem sie niestety rozmija z tym co jest na wykladach :/ Ale coz...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Śro 20:18, 01 Lut 2006    Temat postu:

Ale w linijce wczesniej jest że b nalezy do T* czyli zbioru wszystkich skonczonych słów składających się z terminali...

PS. Czy ktos wie jak wygląda gramatyka dla Ln n n? Nie pamietam czy byla na wykladzie a nie mam sily juz wertowac notatek po raz 2 dzisiaj...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Śro 20:43, 01 Lut 2006    Temat postu:

Cytat:
ramatyki klasy 2 NIE SA podklasa gramatyk klasy 1 gdzyz tutaj slowo puste MOZE wystepowac po prawej stronie. Natomiast jesli wezmiemy klase 2 bez jezykow zawierajacych slowo puste (czyli de facto takich, w ktorych wystepuje produkcja: nieterminal -> slowo puste) to to juz bedzie podklasa klasy 1.

No wg wykładu masz rację... Ale zajrzałem do książki - "Propedeutyka informatyki" Turskiego (którą Ślusarek podawał jako zalecaną literaturę) i tam wyraźnie jest napisane, że w każdej klasie następniki produkcji są niepuste, a następnie, że "każda gramatyka klasy i jest jednocześnie gramatyką klasy j, dla 0<=j<=i"...
A z tymi pojedyńczymi produkcjami w regularnych gramatykach, to rzeczywiście masz rację, u Turskiego jest tak samo, będę musiał skoczyć do ćwiczeniowca wywalczyć trzydziesty punkt za ćwiczenia ;).
Cytat:
To jest oczywiscie podklasa klasy 0. Jedna bardzo wazna rzecz, ktorej nie napisales - slowa pustego nie moze byc po prawej stronie (bo wtedy skracalaby sie dlugosc slowa)

No ale to jest wymuszone przez nieskracanie się słowa, więc nie trzeba tego pisać.


Ostatnio zmieniony przez Madras dnia Śro 20:57, 01 Lut 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Śro 20:58, 01 Lut 2006    Temat postu:

No i badz tu madry i ucz sie do egzaminu... majac trzy rozne wersje tego samego :/

Ostatnio zmieniony przez hansu dnia Śro 21:03, 01 Lut 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Madras
Omylny Admin



Dołączył: 09 Lis 2005
Posty: 2021
Przeczytał: 0 tematów

Skąd: Z Pokoju :]

PostWysłany: Śro 20:58, 01 Lut 2006    Temat postu:

No właśnie... Trzeba wyłapywać takie cholerne drobiazgi :<.
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Paweł Str.
Gość






PostWysłany: Śro 23:01, 01 Lut 2006    Temat postu:

Robson napisał:
PS. Czy ktos wie jak wygląda gramatyka dla Ln n n? Nie pamietam czy byla na wykladzie a nie mam sily juz wertowac notatek po raz 2 dzisiaj...


Nie było to przypadkiem a^n b^n c^n ?
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Śro 23:06, 01 Lut 2006    Temat postu:

Tak, ale mi chodzi o produkcje... próbowałem sam sobie wymysleć ale jakoś mi nie poszło...:P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 0:07, 02 Lut 2006    Temat postu:

S -> aABC | abc
A -> aAB | aX
BC -> bCc
Bb -> bB
Xb -> bX
XC -> bc

Troche mi zagmatwana wyszla ale staralem sie ja zrobic tak, zeby byla klasy 1... Aha, nie recze ze to dziala! Mam nadzieje... ;)


Ostatnio zmieniony przez hansu dnia Czw 0:39, 02 Lut 2006, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 0:31, 02 Lut 2006    Temat postu:

S -> aABC -> aaAbBC -> aaaXbbCc -> aaabXbCc -> aaabbXCc -> aaabbbcc ...
Prawie działa...
Własciwie to podoba mi sie pomysł z tym wędrującym Xem :) ale na wykładzie Ślusarek napisał że każdą produkcję można przedstawić za pomocą k'Ak" -> k'Hk" gdzie A jest nieterminalem, H<>pustego jest podzbiorem (NuT)* (słów nad naszym alfabetem termianli i nieterminali) a k' i k" też sa z niego i to one ustalają ten tak zwany kontekst...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 0:34, 02 Lut 2006    Temat postu:

S -> aABC -> aaAbBC -> aaaAbbBC -> aaaaXbbBC -> aaaabbXBC -> aaaabbXbCc -> aaaabbbXCc -> aaaabbbbcc

chyba nie działa... hmmm chyba, ze gdzieś jest błąd...

---edit----

chyba za długo nad tym myślałem... :)
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 0:39, 02 Lut 2006    Temat postu:

SORRRY!!! tam zamiast A -> aAb | aX ma byc A -> aAB | aX
Juz poprawiam, bije sie w piersi :D
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Paweł Str.
Gość






PostWysłany: Czw 0:42, 02 Lut 2006    Temat postu:

Gramatyka kontekstowa (bo nie ma produkcji skracających ani dających słowo puste):

S-> aXc | e // jedyna dozwolona produkcja do słowa pustego
X-> AXC | b
aA->aa
Cc->bcc
Cb->bC
Powrót do góry
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 0:47, 02 Lut 2006    Temat postu:

Anonymous napisał:
S-> aXc | e // jedyna dozwolona produkcja do słowa pustego


A dlaczego ta produkcja do słowa pustego jest dozwolona..?
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 0:51, 02 Lut 2006    Temat postu:

dla n=0...
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Makros
pijak



Dołączył: 01 Gru 2005
Posty: 420
Przeczytał: 0 tematów

Skąd: Kraków

PostWysłany: Czw 0:54, 02 Lut 2006    Temat postu:

na wykłądzie Ślusarka język Lnnn był definiowany tak a^n b^n c^n gdzie n=1,2,3... (bez 0)

zero było w Lnn....
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
Robson
zielony żul



Dołączył: 21 Paź 2005
Posty: 1274
Przeczytał: 0 tematów

Skąd: Z Lasu :]

PostWysłany: Czw 1:02, 02 Lut 2006    Temat postu:

Aha... cóż... wiele się trzeba jeszcze nauczyć :P
Powrót do góry
Zobacz profil autora
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
hansu
Nieomylny Admin



Dołączył: 17 Lis 2005
Posty: 1990
Przeczytał: 0 tematów

Skąd: przychodzimy? Czym jestesmy? Dokad zmierzamy?

PostWysłany: Czw 1:12, 02 Lut 2006    Temat postu:

To co Pawel Str. napisal jest OK. Tylko bez tego slowa pustego. Mozna by to nawet skrocic do czegos takiego:

S-> aXc
X-> aXC | b
Cc->bcc
Cb->bC

W takiej formie jest po prostu piekna :D Duuuzo lepsza od tej mojej kulawej :P
Powrót do góry
Zobacz profil autora
Wyświetl posty z ostatnich:   
Napisz nowy temat   Odpowiedz do tematu    Forum Informatyka UJ forum Strona Główna -> Archiwum / 1 rok / 1 semestr - Informatyka Wszystkie czasy w strefie EET (Europa)
Strona 1 z 1

 
Skocz do:  
Nie możesz pisać nowych tematów
Nie możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach

fora.pl - załóż własne forum dyskusyjne za darmo
Powered by phpBB © 2001, 2005 phpBB Group
Regulamin