Pytania otagowane jako pumping-lemma

Niezbędne właściwości języków formalnych w niektórych klasach, które polegają na domknięciu przed powtórzeniem pewnych podsłów. Upewnij się, że Twoje pytanie nie jest uwzględnione, stosując techniki z https://cs.stackexchange.com/q/1031/755.

3
Czy język par słów o równej długości, których odległość hamowania wynosi 2 lub więcej, jest pozbawiona kontekstu?
Czy następujący kontekst językowy jest bezpłatny? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Jak wskazał sdcvvc, słowo w tym języku można również opisać jako połączenie dwóch słów o tej samej długości, których odległość młotkowania wynosi …
2
Jak mogę udowodnić, że ten język nie jest pozbawiony kontekstu?
Mam następujący język {0i1j2k∣0≤i≤j≤k}{0i1j2k∣0≤i≤j≤k}\qquad \{0^i 1^j 2^k \mid 0 \leq i \leq j \leq k\} Próbuję ustalić, do której klasy języka Chomsky pasuje. Widzę, jak można to zrobić za pomocą gramatyki kontekstowej, więc wiem, że jest przynajmniej wrażliwa na kontekst. Wydaje się, że nie byłoby możliwe stworzenie gramatyki bezkontekstowej, ale …
1
Pompujący lemat dla deterministycznych języków bezkontekstowych?
Lemat pompujący dla zwykłych języków może być użyty do udowodnienia, że ​​niektóre języki nie są regularne, a lemat pompujący dla języków bezkontekstowych (wraz z lematem Ogdena) może być użyty do udowodnienia, że ​​niektóre języki nie są kontekstowe. Czy istnieje determinujący lemat dla deterministycznych języków bezkontekstowych? To znaczy, czy istnieje lemat …
1
Jak można ws z | w | = | s | a my będziemy bez kontekstu, podczas gdy w # s nie jest?
Dlaczego (jeśli tak) separator ##\# robi różnicę między tymi dwoma językami? Powiedzmy: L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L={ws:|w|=|s|w,s∈{0,1}∗,w≠s}L=\{ws : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L#={w#s:|w|=|s|w,s∈{0,1}∗,w≠s}L_{\#}=\{w\#s : |w|=|s|\, w,s\in \{0,1\}^{*}, w \neq s \} Oto dowód i gramatyk reprezentującyLLL jak CFLCFLCFL A poniżej dodam dowód na to L#∉CFLL#∉CFLL_{\#} \notin CFL : Czy ##\#znak naprawdę …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.