gramatyki bezkontekstowe zadania
sabunia portal
On 06.05.2005, Maciej Misiak <grizzleyWYTNI@op.plwrote:
| Ja również się czegoś dowiedziałem. Tego mianowicie, że nie nadaję się
| na golfistę :P
Ale masz jakieś konkretne argumenty na poparcie tej szalonej tezy?
Owszem, nawet kilka:
* moje rozwiązanie golfowe
* rozwiązania zadań z języków formalnych i teorii obliczeń -- chodzi
głównie o rachunek lambda i gramatyki kontekstowe i bezkontekstowe, bo
z reguły wychodzą mi straszne potworki
Żeby
zrozumieć Twoje rozwiązanie musiałem trochę się doszkolić w referencjach.
Cieszę się, że ktoś skorzystał na moim rozwiązaniu :)
Nawiasem mówiąc, ja to oddałem prowadzącemu. Napisał, że wolno oddać
zadanie w Perlu, więc stwierdziłem, że sam jest sobie winien ;P
A
skoro potrafisz napisać coś tak skomplikowanego, to dokonanie cięć nie powinno
być problemem. Oczywiście trzeba mieć na to czas...
To po raz. Po dwa: trzeba mieć pomysł na cięcie, a u mnie z reguły jest
problem właśnie z pomysłem.
Krzysztof Parzyszek wrote:
Z tego wynika, że ustalenie czy L(CFG) jest regularny jest
nierozstrzygalne :(
Dla dowolnej danej gramatyki bezkontekstowej CFG i jezyka
regularnego LR nie mozna sprawdzic, czy L(CFG) = LR, ale
mozna, czy L(CFG) subseteq LR. Wynika to z tego, ze to,
czy LR subseteq L(CFG) jest nierozstrzygalne. Przyznam, ze
nie widze tego wynikania, bo nie chce sprawdzac, czy L(CFG)
jest rowny dowolnemu LR, tylko czy istnieje takie LR, ze
L(CFG) = LR.
Twoje zagadnienie widzę tak: dajesz użytkownikowi możliwość
zdefiniowania jakiegoś języka. Wymagasz, żeby ten język był
regularny, ale żeby było wygodniej pozwalasz użytkownikowi na
użycie gramatyki bezkontekstowej. Mając taką gramatykę, chcesz
się przekonać, czy nadal definiuje ona język regularny i jeśli nie to
zgłaszasz błąd. W przeciwnym przypadku ``odzyskujesz'' gramatykę
regularną równoważną zadanej gramatyce bezkontekstowej
i dokonujesz jakichś transformacji.
Dokladnie tak wyglada problem.
Przy takim postawieniu problemu jest on w istocie nierozstzrzygalny.
Ale _dlaczego_? :-)
AFAIK minimalny automat (deterministyczny) jest wyznaczony
jednoznacznie z dokładnością do izomorfizmu.
Rowniez mam takie wrazenie, ale tez na zasadzie AFAIK. :-)
Oj, trzeba sie bedzie przeleciec do biblioteki i odswierzyc pamiec.
Pozdrawiam
Piotr Wyderski
Jacek Kijewski wrote:
On Tue, 3 Feb 2004, Radoslaw Zasiadczuk wrote:
| I po PW chcesz być _prawdziwym_ informatykiem? A będziesz specjalizował
| się w systemach masowej obsługi, teorii grafów, teorii automatów
| skończonych, czy może lepiej gramatykach bezkontekstowych?
| Tak z ciekawości pytam...
| przeciez napisal, ze pracuje. nawet jesli bedzie mial dyplom
| z teorii grafow, lata spedzone na polu bitwy uczynia z niego mez..
| ten tego, prawdziwego informatyka ;)
Chyba sie nie zrozumielismy. Prawdziwy informatyk to taki od teorii
grafow, SMO, programowania liniowego, jezykow formalnych...
IC. a jak dostanie zadanie wygrzebania "kto dzis tak zatkal siec"...
Taki, co zarzadza sieciami albo odkurza pecety... to computer technician,
zeby daleko nie szukac i nikogo nie obrazac.
...to mu dyplom przeszkadza w pojsciu tutaj ^^^, gdzie owa informacje
otrzymalby bez pisania wlasnego parsera logow? :)
pozdrawiam,
Radoslaw '' Zasiadczuk
Milo wrote:
Czy moze mi ktos wyjasnic czym sie rozni "zwykla" gramatyka od gramatyki
bezkontekstowej? Pojecie to wystepuje w zadaniach, a nie bardzo widze roznice
(a tak prawde mowiac to nie znam wogole definicji gramatyki bezkontekstowej).
--
Milo
milo@poczta.onet.pl
m@students.mimuw.edu.pl
Algorytm dzialania, ktory doprowadzi Cie do znalezienia odpowiedzi wyglada
tak:
1. Idziemy do biblioteki na MIMUWie
2. Bierzemy do reki ksiazke Hopcrofta i Ullmana "wstep do teorii jezykow i
obliczen" (bodajze)
3. Czytamy.
Jesli chodzisz na wyklad z JAO to nie wierze, aby wykladowca nie podal tej
ksiazki jako literatury.
Khaliff TM
"Modern man is the missing link between apes and human beings."
Cytat
A sami byli dla siebie większym ciężarem niż ciemność. Mdr 17,20
A sami byli dla siebie większym ciężarem niż ciemność. Mdr 17,20_2