Pytania otagowane jako automata

Pytania dotyczące urządzeń matematycznych, które odczytują symbol strumienia wejściowego za pomocą symbolu i używają mapy przejścia stanu do wytworzenia strumienia wyjściowego, być może wykorzystując pamięć dodatkową.

8
Jak udowodnić, że język jest regularny?
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L ′LLLL′L′L' L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}L′:={w∈L:uv=w for u∈Σ∗∖L and v∈Σ+}\qquad \displaystyle …
2
Określanie możliwości min-stosu (lub innych egzotycznych) automatów stanowych
Zobacz koniec tego postu, aby uzyskać wyjaśnienie definicji automatów typu min-heap. Można sobie wyobrazić użycie różnych struktur danych do przechowywania informacji do wykorzystania przez automaty stanów. Na przykład automatyczne automaty przechowują informacje na stosie, a maszyny Turinga używają taśmy. Automaty stanowe korzystające z kolejek oraz te, które używają dwóch wielu …
1
Czy automat zwijający z dwoma stosami jest równoważny maszynie Turinga?
W tej odpowiedzi wspomniano o tym Skończony automat może rozpoznać zwykły język. Język bezkontekstowy wymaga stosu, a język kontekstowy wymaga dwóch stosów (co jest równoważne z twierdzeniem, że wymaga pełnej maszyny Turinga) . Chciałem wiedzieć o prawdzie odważnej części powyżej. Czy to prawda, czy nie? Jaki jest dobry sposób na …
2
Czy istnieją z natury niejednoznaczne i deterministyczne języki bezkontekstowe?
Nazwijmy bezkontekstowy język deterministyczny wtedy i tylko wtedy, gdy może on zostać zaakceptowany przez deterministyczny automat odpychający, a niedeterministyczny inaczej. Nazwijmy język bezkontekstowy z natury dwuznacznym wtedy i tylko wtedy, gdy wszystkie bezkontekstowe gramatyki, które generują ten język, są dwuznaczne, a jednoznaczne inaczej. Przykładem deterministycznego, jednoznacznego języka jest język: Przykładem …
6
Czy są jakieś nieskończone automaty?
W teorii automatów wszyscy od samego początku czytamy automaty jako automaty skończone. Chcę wiedzieć, dlaczego automaty są skończone? Dla jasności, co to jest w skończonym automacie - alfabet, język, ciągi znaków wyrażeń regularnych, czy co? Czy istnieją (teoretycznie) jakieś nieskończone automaty?
2
Dlaczego typ pustki C nie jest analogiczny do typu pusta / dolna?
Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …
28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 
6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
4
Jak symulować odwołania wsteczne, wyprzedzenia i spojrzenia w automatach skończonych?
To pytanie zostało przeniesione z Przepełnienia stosu, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 7 lat temu . Stworzyłem prosty leksymetr i analizator wyrażeń regularnych, aby pobrać wyrażenie regularne i wygenerować jego drzewo analizy. Utworzenie niedeterministycznego automatu skończonego z tego drzewa analizy jest stosunkowo proste w …
1
Zdecyduj, czy języki bezkontekstowe mogą być akceptowane przez deterministyczny automat przesuwania
Biorąc pod uwagę bezkontekstową gramatykę G, istnieje niedeterministyczny automat pushdown N, który akceptuje dokładnie język, który akceptuje G. (i odwrotnie) Nie może również istnieć deterministyczny automat ze stosem D, który akceptuje dokładnie język G akceptuje też. To zależy od gramatyki. Za pomocą jakiego algorytmu produkcji G możemy ustalić, czy D …
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 = …
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.