Pytania otagowane jako formal-languages

Pytania dotyczące języków formalnych, gramatyki i teorii automatów

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 …
6
Jaki jest związek między językami programowania, wyrażeniami regularnymi i językami formalnymi
Rozejrzałem się w sieci, szukając odpowiedzi na to pytanie i wydaje się, że wszyscy domyślnie znają odpowiedź oprócz mnie. Przypuszczalnie dzieje się tak, ponieważ jedynymi osobami, które się opiekują, są osoby z wyższym wykształceniem na ten temat. Z drugiej strony zostałem wrzucony w głęboki koniec za zadanie do szkoły średniej. …
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn Turinga i języków formalnych? Zauważam, że prawie każdy …
1
Czy istnieje jakiś nieogólny algorytm analizowania CFG, który rozpoznaje EPAL?
EPAL, język parzystych palindromów, jest definiowany jako język generowany przez następującą jednoznaczną, bezkontekstową gramatykę: S→aaS→aaS \rightarrow a a S→bbS→bbS \rightarrow b b S→aSaS→aSaS \rightarrow a S a S→bSbS→bSbS \rightarrow b S b EPAL jest „zmorą” wielu algorytmów parsowania: jeszcze nie spotkałem się z żadnym algorytmem parsowania dla jednoznacznych CFG, które …
1
Jak pokazać, że L = L (G)?
Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie pożądane słowa. Często możemy dyskutować na wysokim szczeblu, dlaczego …
2
Czy istnieje „naturalny” nierozstrzygalny język?
Czy istnieje jakiś „naturalny” język, który jest nierozstrzygalny? przez „naturalny” rozumiem język zdefiniowany bezpośrednio przez właściwości ciągów, a nie przez maszyny i ich odpowiedniki. Innymi słowy, jeśli język wygląda jak gdzie to TM, DFA (lub regularny exp), PDA (lub gramatyka) itp., To nie jest naturalne. Jednak jest naturalne.L={⟨M⟩∣…}L={⟨M⟩∣…} L = …
1
Maszyny dla języków bezkontekstowych, które nie zyskują dodatkowej mocy z niedeterminizmu
Rozważając modele maszynowe obliczeń, hierarchię Chomsky'ego zazwyczaj charakteryzuje (w kolejności), automat skończony, automat push-down, automat liniowo związany i maszyny Turinga. W przypadku pierwszego i ostatniego poziomu 1 (języki zwykłe i języki z wyliczaniem rekurencyjnym) nie ma różnicy w sile modelu, czy rozważamy maszyny deterministyczne czy niedeterministyczne, tj. DFA są równoważne …
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.