Mam jutro kolokwium, a na nim m.in. LOP.
Z materiałów od wykładowcy mam: QPfzwU5.jpg
Mógłby ktoś to wyjaśnić łopatologicznie? Bo cały dzień siedzę i nie mogę zrozumieć
dodanie obrazka do załączników posta - @furious programming
0
0
kompilatory.agh.edu.pl/pages/ta-wyklady/3-6-wlasciwosci-jezykow-bezkontekstowych.htm
kompilatory.agh.edu.pl/pages/ta-zadania/ Zadania07-wlasnosci-jbezkontekstowych.htm
Chciałbym pomoc bardziej ale mam pod ręką tylko telefon a to nie zachęca do długich postów.
0
Sęk w tym, że to też naukowy bełkot (tak to nazwę). Mnie chodzi o prostsze podejście do tego
1
Ale właściwie czego oczekujesz? To jest proste twierdzenie. Masz podany algorytm którym możesz udowodnić że język nie jest bezkontekstowy. Nie musisz tego specjalnie rozumieć żeby rozwiązać zadanie :) ale jeśli bardzo chcesz to w 1 linku masz szkic dowodu.
0
Chodzi o Lemat o pompowaniu przy dowodzeniu że język nie jest regularny a nie o gr. bezkontekstową.
Nie rozumiem począwszy od A = a{3N} b{N+1}
bo skąd tutaj bierze się N+1 skoro L={an bm}
Potem jak się buduje słowo A z BCD
Potem tego BC4 = ...
1
Ech.
N+1 jest stąd że m jest większe od n, więc musi wynosić przynajmniej n+1.
Nic się z niczego nie buduje. Lemat o pompowaniu zakłada że możesz podzielić słowo na 3 kawałki, oznaczone tu jako B C i D.
Powtórzenie C to przecież sens tego lematu! To jest pompowanie właśnie. Ty w ogóle wiesz jaką jest treść tego lematu?
0
N+1 jest stąd że m jest większe od n, więc musi wynosić przynajmniej n+1.
Nie zauwazylem zalozenia n<m
Nic się z niczego nie buduje. Lemat o pompowaniu zakłada że możesz podzielić słowo na 3 kawałki, oznaczone tu jako B C i D.
Jak słowo się dzieli? Sa jakieś zasady?
Powtórzenie C to przecież sens tego lematu! To jest pompowanie właśnie. Ty w ogóle wiesz jaką jest treść tego lematu?
Chodzi mi o to co jest po "równa się" BC^4D
0
Weź łaskawie przeczytaj ten lemat. Serio. Bez tego się nie da. Lemat mówi że jeśli da się słowo z danego języka podzielić na kawałki spełniające pewne warunki to można pompować to słowo a wynik pompowania będzie należał do języka. Jeśli nie jest to spełnione to język nie jest regularny. Więc zwykle robisz dowód nie-wprost. Zakładasz że język jest regularny a potem pokazujesz że istnieje słowo spełniające założenia lematu ale które po pompowaniu nie należy do języka.
Chyba oblejesz tego kolosa...