JFiZO - Zadanie 09.040

Załóżmy, że L - język tych palindromów nad alfabetem {0,1}*, które mają taką samą ilość zer i jedynek jest bezkontekstowy.
Rozważmy słowo w = 0^N1^{2N}0^N, gdzie N jest stałą z lematu o pompowaniu.
Jakikolwiek podział sztyx słowa „w” sobie nie wybierzemy to znajdziemy takie k, że sz^kty^ks nie należy do L,
ponieważ albo zaburzy nam się równowaga liczb albo palindromowość.

 
jfizo/zadanie09.040.txt · ostatnio zmienione: 2010/03/21 15:28 przez alistra
 
Wszystkie treści w tym wiki, którym nie przyporządkowano licencji, podlegają licencji:MIT License
Recent changes RSS feed