Pytania otagowane jako regular-languages

Pytania dotyczące właściwości klasy zwykłych języków i poszczególnych języków.

4
Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią)
Problem Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego. Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter.w=x1…xnw=x1…xnw=x_1…x_n Regex: wyrażenie regularne. Dla weryfikacji: „Permutacje regexów bez powtórzeń” Odpowiedź tworzy kod JavaScript zamiast wyrażenia regularnego, zakładając, że byłoby to prostsze. „Jak znaleźć wszystkie permutacje …
3
Zwykłe języki, których nie można wyrazić za pomocą tylko 2 operacji wyrażenia regularnego
Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki) trzymać. Powiedziano mi na przykład, że jeśli mogę korzystać tylko z operacji wyrażenia …
2
Maszyny Turinga z pojedynczą taśmą z wejściem chronionym przed zapisem rozpoznają tylko zwykłe języki
Oto problem: Udowodnij, że maszyny Turinga z pojedynczą taśmą, które nie mogą pisać na części taśmy zawierającej łańcuch wejściowy, rozpoznają tylko zwykłe języki. Moim pomysłem jest udowodnienie, że ta konkretna baza TM jest odpowiednikiem DFA. Używanie tej TM do symulacji DFA jest bardzo proste. Jednak gdy chcę użyć tego DFA …
2
Jeśli
Na przykład, L⊆{0}∗L⊆{0}∗L \subseteq \{0\}^* . Jak więc możemy udowodnić, że L∗L∗L^* jest regularne? Jeśli LLL jest regularne, to oczywiście L∗L∗L^* jest również regularne. Jeśli LLL jest skończone, to jest regularne i znowu L∗L∗L^* jest regularne. Zauważyłem również, że dla L={0p∣p is a prime}L={0p∣p is a prime}L = \{0^p \mid …
7
Czy
Jeśli jest regularne, to czy wynika z tego, że jest regularne? AA2A2A^2AAA Moja próba na dowód: Tak, ponieważ sprzeczność zakłada, że nie jest regularne. Następnie .A 2 = A ⋅ AAAAA2=A⋅AA2=A⋅AA^2 = A \cdot A Ponieważ łączenie dwóch nieregularnych języków nie jest regularne, nie może być regularne. Jest to sprzeczne …
2
Czy wszystkie języki bezkontekstowe i zwykłe są skutecznie rozstrzygalne?
Natknąłem się na ten rysunek, który pokazuje, że języki kontekstowe i zwykłe są (odpowiednimi) podzbiorami sprawnych problemów (podobno ). Doskonale rozumiem, że wydajne problemy stanowią podzbiór wszystkich rozstrzygalnych problemów, ponieważ możemy je rozwiązać, ale może to zająć bardzo dużo czasu.P.P\mathrm{P} Dlaczego wszystkie bezkontekstowe i regularne języki są skutecznie rozstrzygalne? Czy …
4
Język bez gwiazdek a język zwykły
Zastanawiałem się, ponieważ * jest sam język gwiazda wolna, czy istnieje język regularny, który nie jest językiem gwiazdy darmo? Czy możesz podać przykład?za∗za∗a^* (z wikipdii ) Lawson definiuje języki bez gwiazdek jako: Mówi się, że w zwykłym języku nie ma gwiazd, jeśli można go opisać wyrażeniem regularnym zbudowanym z liter …
1
Wykazać, że dopełnienie
Chcę udowodnić, że dopełnienie nie używa regularnie właściwości zamknięcia.{ 0n1n| N ≥0 }{0n1n∣n≥0}\{0^n1^n \mid n \geq{} 0\} Rozumiem, że można użyć lematu pompującego, aby udowodnić, że nie jest zwykłym językiem. Rozumiem również, że zwykłe języki są zamknięte w ramach operacji uzupełniania. Czy to jednak oznacza również, że uzupełnienie języka nieregularnego …
3
Dlaczego wyrażenia regularne są definiowane za pomocą operacji łączenia, łączenia i operacji gwiazdowych?
Regularne expresssion jest zdefiniowany rekurencyjnie jako aaa dla niektórych jest wyrażeniem regularnym,a∈Σa∈Σa \in \Sigma εε\varepsilon jest wyrażeniem regularnym, ∅∅\emptyset jest wyrażeniem regularnym, (R1∪R2)(R1∪R2)(R_1 \cup R_2) gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,R1R1R_1R2R2R_2 (R1∘R2)(R1∘R2)(R_1 \circ R_2) gdzie i są wyrażeniami regularnymi, jest wyrażeniem regularnym,R1R1R_1R2R2R_2 (R1)∗(R1)∗(R_1)^* gdzie jest wyrażeniem regularnym jest …
1
Algorytm sprawdzający, czy język jest prawidłowy
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest prawidłowy? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak L={anbn:n∈N}L={anbn:n∈N}L=\{a^n b^n : n \in \mathbb{N}\}), sprawdź, czy język jest prawidłowy, czy nie. Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich …
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.