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.
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...
Wikipedia ma następującą definicję lematu pompującego dla zwykłych języków ... Niech będzie zwykłym językiem. Następnie istnieje całkowita p ≥ 1 zależy wyłącznie od L , tak że każdy ciąg wagowych w L o długości co najmniej p ( p nazywany jest „pompowanie długość”) może być zapisane jako W = xyz...
Próbuję użyć lematu pompującego, aby udowodnić, że nie jest regularne.L = { ( 01 )m2)m∣ m ≥ 0 }L={(01)m2m∣m≥0}L = \{(01)^m 2^m \mid m \ge0\} Oto co mam do tej pory: Załóżmy, że jest regularne i niech p będzie długością pompowania, więc w = ( 01 ) p 2 p . Rozważ każdy rozkład pompowania w = x y z...
Tak więc w zasadzie L spełnia warunki pompowania lematu dla CFL, ale nie jest CFL (jest to możliwe zgodnie z definicją
Zastanawiałem się, kiedy języki zawierające taką samą liczbę wystąpień dwóch podciągów będą normalne. Wiem, że język zawierający taką samą liczbę 1 i 0 nie jest regularny, ale jest językiem takim jak , gdzie = liczba wystąpień podłańcucha „001” jest równa liczbie wystąpień podłańcucha „ 100 "...
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...
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...
Opisz zwykły język, którego nie może zaakceptować żaden DFA, który ma tylko trzy stany. Nie jestem do końca pewien, od czego zacząć i zastanawiałem się, czy ktoś mógłby dać mi jakieś wskazówki lub porady. Rozumiem, że lematu pompującego można użyć do udowodnienia, że język nie jest regularny,...
Biorąc pod uwagę język , jak mogę powiedzieć bezpośrednio, nie patrząc na reguły produkcji, że ten język nie jest regularny?L = {zanbndon}L.={zanbndon} L= \{a^n b^n c^n\} Mógłbym użyć lematu pompującego, ale niektórzy mówią tylko patrząc na gramatykę, że to nie jest normalne. Jak to jest...