JFIZO - Zadanie 09.038

Zadanie. Czy L = \{ vww : v, w \in \{a, b, c\}^*, w \not= \epsilon \} jest bezkontekstowy?

Nie jest.

Dowód. Przekroić L z c^*b^*ac^*b^*a i wziąć słowo c^Nb^Nac^Nb^Na.

Kontrprzykład: podział na sztyx może być taki, że z i y zawierają tylko c z pierwszego c^n. Wtedy pompując dodatkowe c zachowujemy warunek wyrażenia regularnego oraz warunek oryginalnego języka (bo dodatkowe c możemy wepchnąć do prefiksu v)

To można łatwo naprawić przecinając L z L_{ac^*b^*aac^*b^*a}.