Informatyka UJ forum

Skrobocik

Jak to jest z tym udowadnianiem, że jakiś język/gramatyka/automat jest regularny/kontekstowy/bezkontekstowy i tak dalej :?:

Wiem, że stosuje się lematy o pompowaniach. Czy coś jeszcze :?:
Jakby ktoś mógł się oderwać na chwilkę od RPS i wyjaśnić mi to mniej więcej......

Rogal

Zwykły automaty skończony rozpoznaje tylko języki regularne...

Gramatyka w jakiej jest klasie to się pokazuje z definicji danej klasy (definicje są właśnie dla gramatyk)

Co do języków...
Regularność pokazuje się przez pompowanie pierwsze.
Co do bezkontekstowości, to jej brak można pokazać przez niespełnienie lematu o pompowaniu drugiego. Nie mniej jednak spełnienie lematu nie oznacza od razu, że język jest bezkontekstowy, do tego służy jakiś inny lemat którego nazwy nie pamiętam.
Generalnie jednak zawsze można próbować tworzyć gramatykę rozpoznającą dany język i należącą do takiej klasy jaką chcemy udowodnić. Ja przynajmniej tak bym dowodził, że coś jest kontekstowe, względnie nawet że jest bezkontekstowe.

edited:
Pytanie - haczyk: Czy każdy język ma jakąś gramatykę która go rozpoznaje?

dzendras

Od RPSu oderwałem się dzisiaj rano :]

Jeśli chodzi o gramatyki, to patrzysz na postaci produkcji (na ważniaku są podane reguły dla 4 klas gramatyk)

Jeśli chodzi o języki to mamy lematy o pompowaniu. Oby dwa lematy (dla regularnych i bezkontekstowych) mówią tyle, że jeśli jakiś jest regularny/kontekstowy, to spełnia odpowiedni lemat. Jako, że mamy tu implikację, to może się tak zdarzyć (zad 3 z 04_tja_sesyjny.pdf), że język spełnia założenia lematu, ale reularnym/bezkontekstowym nie jest.

Jeśli chodzi o automaty, to automaty zwykłe rozpoznają języki regularne, natomiast automaty ze stosem bezkontekstowe. Wiedząc z jakim automatem masz do czynienia, wiesz jaki język ten automat rozpoznaje.

EDIT: @rogal: Gwoli ścisłości, to gramatyka raczej generuje niż rozpoznaje.
A jeśli chodzi o odp, to raczej nie. Np języki naturalne. Chomsky się chyba na tym przejechał właśnie...

Rogal

Otóż, języków nad alfabetem {a,b} jest continuum, a gramatyk tylko przeliczalnie wiele, więc istnieje bardzo dużo języków, dla których nie istnieje gramatyka.

Co do języków naturalnych to odpowiedź będzie: zdecydowanie tak. Wszystko się wali na językach nieskończonych, każdy skończony (a takie są naturalne) da się wyifować w stylu:
S -> kot
S -> pies
S -> drzewo
itp.
Tak samo da się wyifować każdą konstrukcję gramatyczną.

Aha, skoro już się rozpisałem, to każdy język skończony jest regularny :wink:

Robson

Dobra... a teraz inne pytanie... czy monoid przemienny generowany przez wiecej niz jeden element moze być monoidem wolnym?...

kg86

skoro kazdy element, musi miec jednoznaczy rozklad na elementy zbioru S/S^2, to zbior S/S^2 musi sie skladac z niemniejszej liczby elementow, niz zbior generatorow [w przeciwnym razie, nie kazdy element daloby sie rozlozyc na elementy tego zbioru], wiec zbior S/S^2 zawiera wiecej niz jeden element, np. elementy a i b :) a poniewaz monoid jest przemienny, wiec a*b = b*a = c, co nie wiem czy mozna uznac za 2 rozne rozklady elementu c :P ale jesli tak, to nie istnieje :) w przeciwnym razie nie wiem :P

Robson

No własnie ja tez.....:P

Rogal

Wygląda na to, że przemienne monoidy z bazą większą niż 1 są szybkie z definicji.