Przykład bezkontekstowego języka, który mimo to MOŻE być pompowany?

Tak więc w zasadzie L spełnia warunki pompowania lematu dla CFL, ale nie jest CFL (jest to możliwe zgodnie z definicją lematu).

formal-languages context-free pumping-lemma użytkownik2329564
źródło

Czy to pytanie do pracy domowej, czy jesteś po prostu ciekawy?

Yuval Filmus

To nie jest zadanie domowe, ale spodziewam się, że zobaczę to na egzaminie (tylko przeczucie, znając mojego profesora). I zawsze jestem ciekawy :)

user2329564

Mieliśmy podobne pytanie, ale dotyczy to zwykłych języków . Obowiązuje ten sam typ konstrukcji: weź specjalny symbol i rozważ dla nieprzyjemnego języka .

$

$\$$

$ K \cup {$^{k} ∣ k \neq 1} {a, b}^{*}

$\$K \cup \{ \$^k \mid k \neq 1\}\{a,b\}^*$

K \subseteq {a, b}^{*}

$K\subseteq \{a,b\}^*$

Hendrik,

Odpowiedzi:

Klasycznym przykładem jest . Mądry pokazuje w swojej pracy Silny lemat pompowania dla języków bezkontekstowych, że ani Barem-Hillela, ani lemona Parikha (stwierdzająca, że zestaw długości słów w języku bezkontekstowym jest półliniowy), mogą być użyte do udowodnienia że nie jest kontekstem. Inne sztuczki, takie jak przecinanie zwykłego języka, również nie pomagają. (Lemat Ogdena, uogólnienie lematu pompującego Bar-Hillela, dowodzi, że nie jest pozbawiony kontekstu.) Zapewnia również alternatywny lemat pompowania, który jest równoważny bezkontekstowości (dla języków obliczalnych) i używa go do udowodnienia że nie jest kontekstem. $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$ $L$ $L$ $L$

Wise stany pompowania lematu, że język jest kontekst wolne wtedy i tylko wtedy, gdy jest (bez ograniczeń) gramatyki wytwarzające jest liczbą całkowitą i tak, że gdy generuje „zdań, formy” (a więc mogą obejmować nie-zaciski) o długości , możemy napisać gdzie są niepuste, , a istnieje nieterminalny taki że generuje a generuje zarówno jak i . $L$ $G$ $L$ $k$ $G$ $s$ $s$ $|s| > k$ $s = uvxyz$ $x,vy$ $|vxy| \leq k$ $A$ $G$ $uAz$ $A$ $vAy$ $x$

Poprzez wielokrotne stosowanie warunku w lemacie, Wise jest w stanie udowodnić, że nie jest pozbawiony kontekstu, ale szczegóły są nieco skomplikowane. Podaje również bardziej skomplikowany równoważny warunek i wykorzystuje go, aby udowodnić, że języka nie można zapisać jako skończonego przecięcia języków bezkontekstowych. $L$ $\{ a^n b a^{nm} : n,m > 0 \}$

Jeśli nie możesz uzyskać dostępu do artykułu Wise'a (znajduje się za zapłatą), istnieje wersja napisana na maszynie, która ukazała się jako raport techniczny uniwersytetu Indiana.

Nie kontekstowy język, który spełnia warunek pompowania lematu Ogdena, podają Johnsonbaugh i Miller, Converse pompowania lematów , i przypisuje się go Boassonowi i Horvathowi, W językach spełniających lemat Ogdena . Językiem, o którym mowa, jest Możemy napisać , odpowiadające dwóm różnym . Zauważ, że i że jest regularny. Lemat Ogdena można wykorzystać do udowodnienia, że

\begin{aligned} L^{'} & = ⋃_{n \geq 1} (e^{+} a^{+} d^{+})^{n} (e^{+} b^{+} d^{+})^{n} (e^{+} c^{+} d^{+})^{n} \\ \cup (a + b + c + d) Σ^{*} \cup Σ^{*} (a + b + c + e) \cup Σ^{*} (e d + d (a + b + c) + (a + b + c) e) Σ^{*} . \end{aligned}

$\begin{align*} L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n \\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*. \end{align*}$

L^{'} = L_{1} \cup L_{2}

$L' = L_1 \cup L_2$

L_{1} \cap L_{2} = \emptyset

$L_1 \cap L_2 = \emptyset$

L_{2}

$L_2$

L_{1}

$L_1$ nie jest kontekstem, podobnie jak , ale nie można go użyć bezpośrednio do wykazania, że nie jest kontekstem.

L^{'}

$L'$

L^{'}

$L'$

Yuval Filmus
źródło

Czy nie musi to być co najmniej jedna produkcja wyglądająca tak: A -> sententialForm1 SententialForm2, aby możliwe było dowolne pompowanie

użytkownik2329564

Cóż bardziej ogólnie: czy nie jest konieczne, aby nieterminalny B był częścią formy sentymentalnej pochodzącej z A, tak że B-> sententialForm1.B.sentential from 2 jest produkcją G. W przeciwnym razie, jak byłoby pewne, że słowo dowolną długość można przepompować z A.

użytkownik2329564

Nie rozumiem dlaczego, mamy produkcję , która odpowiada pompowaniu. Na przykład natychmiast odzyskujesz lemat pompowania, ponieważ .

A \Rightarrow^{+} v A y

$A \Rightarrow^+ vAy$

S \Rightarrow^{*} u A z \Rightarrow^{*} u v^{i} A y^{i} z \Rightarrow^{*} u v^{i} x y^{i} z

$S \Rightarrow^* uAz \Rightarrow^* uv^iAy^iz \Rightarrow^* uv^ixy^iz$

Yuval Filmus

Brzmi jak miły dodatek do naszej referencji .

Raphael

Kolejną rzeczą, której brakuje, jest zamknięcie w „odwrotnych mapowaniach gsm”, patrz planetmath.org/generalizedsequentialmachine . Być może dodam je w pewnym momencie.

Yuval Filmus

Jeszcze prościej: . Można zawsze pompie s; przecięcie ze zwykłym daje brak CFL (i można to udowodnić przez pompowanie lematu). $\{a^m b^n c^n d^n\colon m \ge 1, n \ge 1\}$ $a$ $\mathcal{L}(a b^+ c^+ d^+)$

vonbrand
źródło

Będzie to miły dodatek do trzeciej pracy domowej ... muahaha

Renato Sanhueza

Nie sądzę, że to prawda. Jeśli rozpocznie się językiem z jedynie jeden

, a następnie, jeśli starają się pompować

trzeba uwagę na fakt, że

musi być również w języku.

a

$a$

a

$a$

a^{0}

$a^0$

MCT

Aby rozwinąć komentarz MCT: rozważ słowo

; wybierz

. Zatem dla

nie jest w języku, ponieważ nie zaczyna się od a, więc lemat nie ma miejsca.

a b^{p} c^{p} d^{p}

$ab^pc^pd^p$

v = a

$v=a$

u = w = x = ε

$u=w=x=\varepsilon$

y = b^{p} c^{p} d^{p}

$y=b^pc^pd^p$

i = 0

$i=0$

u v^{i} w x^{i} y

$uv^iwx^iy$

potestasity,

Prostym językiem jest . Przecinaj się z aby uzyskać wyraźnie brak CFL, ale zawsze możesz pompować i naśladować równość długości w morzu $\{a b^n c^n d^n \colon n \ge 1\} \cup \mathcal{L}(a a^+ b^+ c^+ d^+)$ $\mathcal{L}(a b^+ c^+ d^+)$ $a$ . ${}^+$

vonbrand
źródło

Przykład Wise'a jest (najwyraźniej) również odporny na te techniki, a przynajmniej tak twierdzi.

Yuval Filmus

@YuvalFilmus, jak się wydaje. Ale mój przykład jest odporny na to, że profesorowie wątpią w zrozumienie pracy Wise'a lub chcą pełnego dowodu, że nie jest to CFL w 2-godzinnym limicie egzaminu ;-)

vonbrand