[Gramatyki] Lemat o pompowaniu

[turson]

Czyli po prostu po pompowaniu mamy więcej \(\displaystyle{ a}\) niż \(\displaystyle{ b}\), a to jest sprzeczne z założeniami języka?

Jeszcze jedna sprawa, że do zrobienia mam trudniejszy przykład niż ten.
Mianowicie
\(\displaystyle{ L=a^n b^k a^3 : 0 \le n < k}\)

Przyjmuję, że jest to język regularny i istnieje liczba naturalna \(\displaystyle{ N}\) spełniająca tezę LOP.
\(\displaystyle{ a^N b^{N+1} a^3}\)
b ma być więcej niż a dlatego dałem \(\displaystyle{ N+1}\)

Dzielę teraz to na podsłowa BCD zgodnie z założeniami LOP
\(\displaystyle{ A=BCD
\\ B=a^p
\\ C=a^q
\\D = a^{N+1} a^3}\)
wynika stąd, że BC składa się jedynie z symboli \(\displaystyle{ a}\), których jest mniej niż symboli \(\displaystyle{ b}\)
pompowanie
\(\displaystyle{ BC^3D=a^p a^{q \cdot 3} b^{N+1} a^3}\)
wynika stąd, że
\(\displaystyle{ BC=a^p a^{q \cdot 3}
\\|BC| = p+(q \cdot 3)}\)
tutaj wychodzi, że symboli \(\displaystyle{ a}\) jest więcej niż \(\displaystyle{ b}\), a \(\displaystyle{ b}\) miało być więcej niż \(\displaystyle{ a}\), więc dopompowane słowo nie należy do języka \(\displaystyle{ L}\) i język nie jest regularny.

Teraz dobrze rozumiem? Mam kolokwium za godzine...

[Afish]

Czyli po prostu po pompowaniu mamy więcej \(\displaystyle{ a}\) niż \(\displaystyle{ b}\), a to jest sprzeczne z założeniami języka?

Tak, chociaż założenie jest tutaj złym słowem. Po prostu słowo nie należy do języka, a gdyby język był regularny, to po napompowaniu ciągle by należało.

Dzielę teraz to na podsłowa BCD zgodnie z założeniami LOP
\(\displaystyle{ A=BCD
\\ B=a^p
\\ C=a^q
\\D = a^{N+1} a^3}\)

\(\displaystyle{ D}\) jest źle. Po pierwsze masz literówkę (miało być \(\displaystyle{ b}\)), po drugie w lemacie masz, że \(\displaystyle{ |BC| \le N}\), więc w \(\displaystyle{ D}\) może być też literka \(\displaystyle{ a}\), a dokładniej może ich być \(\displaystyle{ a^{N-p-q}}\).

pompowanie
\(\displaystyle{ BC^3D=a^p a^{q \cdot 3} b^{N+1} a^3}\)
wynika stąd, że
\(\displaystyle{ BC=a^p a^{q \cdot 3}
\\|BC| = p+(q \cdot 3)}\)

A tu jest pokłosie poprzedniego błędu. Nie wiesz, czy po trzykrotnym napompowaniu część \(\displaystyle{ BC}\) ma wystarczająco dużo literek. Ale wiesz, że \(\displaystyle{ C}\) jest niepuste, więc ma co najmniej jedną literkę, dlatego jak napompujesz \(\displaystyle{ N+1}\) razy, to na pewno powstałe słowo będzie poza językiem. Poza tym idea się zgadza.

No i do pełni szczęścia wypadałoby jeszcze rozważyć sytuację, gdy \(\displaystyle{ N}\) jest równe \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\), bo wtedy użyte przez Ciebie słowo nie rozłoży się tak łatwo. Zawsze możesz dla świętego spokoju przyjąć coś postaci \(\displaystyle{ a^{N+5}B^{N+6}a^3}\), wtedy nawet dla problematycznej stałej wszystko się zgodzi. Możesz też pokazać, że \(\displaystyle{ N}\) będzie musiało być \(\displaystyle{ >1}\), ale to niekonieczna gimnastyka.

[turson]

Dzielę teraz to na podsłowa BCD zgodnie z założeniami LOP
\(\displaystyle{ A=BCD
\\ B=a^p
\\ C=a^q
\\D = a^{N+1} a^3}\)

\(\displaystyle{ D}\) jest źle. Po pierwsze masz literówkę (miało być \(\displaystyle{ b}\)), po drugie w lemacie masz, że \(\displaystyle{ |BC| \le N}\), więc w \(\displaystyle{ D}\) może być też literka \(\displaystyle{ a}\), a dokładniej może ich być \(\displaystyle{ a^{N-p-q}}\).

Tak literówka i faktycznie jeszcze tam może być \(\displaystyle{ a}\) co rozumiem

pompowanie
\(\displaystyle{ BC^3D=a^p a^{q \cdot 3} b^{N+1} a^3}\)
wynika stąd, że
\(\displaystyle{ BC=a^p a^{q \cdot 3}
\\|BC| = p+(q \cdot 3)}\)

A tu jest pokłosie poprzedniego błędu. Nie wiesz, czy po trzykrotnym napompowaniu część \(\displaystyle{ BC}\) ma wystarczająco dużo literek. Ale wiesz, że \(\displaystyle{ C}\) jest niepuste, więc ma co najmniej jedną literkę, dlatego jak napompujesz \(\displaystyle{ N+1}\) razy, to na pewno powstałe słowo będzie poza językiem. Poza tym idea się zgadza.

\(\displaystyle{ |BC^{N+1}|=p \cdot q \cdot (N+1)}\)
Tutaj już nie ma ilości \(\displaystyle{ a}\) mniejszej od \(\displaystyle{ b}\)
To jest ten dowód dowodzący temu, że dopompowane słowo nie należy do języka?

[Afish]

\(\displaystyle{ |BC^{N+1}|=p \cdot q \cdot (N+1)}\)
Tutaj już nie ma ilości \(\displaystyle{ a}\) mniejszej od \(\displaystyle{ b}\)
To jest ten dowód dowodzący temu, że dopompowane słowo nie należy do języka?

Raczej \(\displaystyle{ p + q\cdot (N+1)}\). Z tego wynika, że literek \(\displaystyle{ a}\) jest co najmniej \(\displaystyle{ 1 + 1\cdot(N+1) = N+2}\), czyli jest ich więcej niż \(\displaystyle{ b}\), więc słowo nie należy do języka.

[turson]

Wracam do tematu. Postaram się sam rozwiązać przykład i liczę na Waszą pomoc w przypadku jakichś ewentualnych błędów.

Mamy język
\(\displaystyle{ L = \{a^n b^m a^3 : n < m \}}\)
Przypuśćmy, że \(\displaystyle{ L}\) należy do zbioru języków regularnych. Zatem istnieje liczba \(\displaystyle{ N \in \mathbb{N}}\), dla której zachodzi teza Lematu o Pompowaniu. (tak nas wykładowca nauczył)
Rozważmy \(\displaystyle{ A = a^N b^{N+1} a^3}\)
Niech \(\displaystyle{ B, C, D}\) spełniają warunki LOP:
\(\displaystyle{ a) A=BCD
\\b) |BC| \le N
\\c) |C| \ge 1}\)
Wynika stąd iż zarówno B jak i C składają się jedynie z symboli \(\displaystyle{ a}\), których jest \(\displaystyle{ p}\) i \(\displaystyle{ q}\)
\(\displaystyle{ B=a^p
\\ C=a^q
\\ D = a^{N-p-q} b^{N+1} a^3}\)

Pompowanie \(\displaystyle{ C}\) o \(\displaystyle{ N+1}\)
\(\displaystyle{ BC^{N+1}D = a^p a^{q \cdot (N+1)} a^{N-p-q} b^{N+1} a^3}\)
zatem
\(\displaystyle{ |BC^{N+1}| = p + q \cdot (N+1)}\)
Z tego wynika, że literek \(\displaystyle{ a}\) jest co najmniej \(\displaystyle{ 1+1\cdot(N+1)=N+2}\), czyli jest ich więcej niż \(\displaystyle{ b}\) (a miało być mniej), więc słowo nie należy do języka \(\displaystyle{ L}\)

[Afish]

Wygląda sensownie.

[turson]

Wreszcie

Jest kolejna część tego zadania. Mianowicie: uzasadnij, że jest to język bezkontekstowy. Jak?

[Afish]

Pokazać gramatykę bezkontekstową, która ten język generuje, albo pokazać niedeterministyczny automat ze stosem dla tego języka.