Informatyka UJ forum

ostoj

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...

Fidel

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

Madras

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.

ostoj

a jak to wy glada ze slowami pustymi? gdzie moga sie pojawiac a gdzie nie?

Madras

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.

ostoj

dzieki Madras

hansu

Pozwole sobie na pewna polemike ;P

Madras

hansu

Dalej sie bede polemizowal :P

Robson

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...

Madras

hansu

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

Madras

No właśnie... Trzeba wyłapywać takie cholerne drobiazgi :<.

Paweł Str. · Gość

Robson

Tak, ale mi chodzi o produkcje... próbowałem sam sobie wymysleć ale jakoś mi nie poszło...:P

hansu

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... ;)

Robson

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...

Makros

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... :)

hansu

SORRRY!!! tam zamiast A -> aAb | aX ma byc A -> aAB | aX
Juz poprawiam, bije sie w piersi :D

Paweł Str. · Gość

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

Makros

Robson

dla n=0...

Makros

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....

Robson

Aha... cóż... wiele się trzeba jeszcze nauczyć :P

hansu

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