Pytania otagowane jako formal-languages

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

4
Jak przekonwertować skończone automaty na wyrażenia regularne?
Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane. Jakie są algorytmy przekształcania NFA w równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub …
5
Jak udowodnić, że język nie jest pozbawiony kontekstu?
Dowiedzieliśmy się o klasie języków bezkontekstowych . Charakteryzuje się zarówno gramatykami bezkontekstowymi, jak i automatami pushdown, dzięki czemu łatwo jest pokazać, że dany język jest pozbawiony kontekstu.CFLCFL\mathrm{CFL} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich gramatyk (lub automatów), że nie potrafią …
10
Jak udowodnić, że język nie jest regularny?
Dowiedzieliśmy się o klasie języków zwykłych . Charakteryzuje go dowolna koncepcja wśród wyrażeń regularnych, automatów skończonych i gramatyk lewostronnych, więc łatwo jest wykazać, że dany język jest regularny.REGREG\mathrm{REG} Jak jednak pokazać coś przeciwnego? Moja TA była nieugięta, że ​​aby to zrobić, musielibyśmy wykazać dla wszystkich wyrażeń regularnych (lub dla wszystkich …
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 …
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 …
2
Dlaczego zwykły język nazywa się „zwykłym”?
Właśnie zakończyła pierwszy rozdział Wprowadzenie do teorii obliczeń przez Michaela Sipser który wyjaśnia podstawy automatów skończonych. Definiuje zwykły język jako wszystko, co można opisać za pomocą automatów skończonych. Ale nie mogłem znaleźć, gdzie tłumaczy, dlaczego zwykły język nazywa się „zwykłym”. Jakie jest pochodzenie terminu „regularny” w tym kontekście? UWAGA: Jestem …
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 …
2
Jak udowodnić, że język jest pozbawiony kontekstu?
Istnieje wiele technik, aby udowodnić, że język nie jest pozbawiony kontekstu, ale jak udowodnić, że język jest pozbawiony kontekstu? Jakie są techniki, aby to udowodnić? Oczywiście jednym ze sposobów jest wykazanie gramatyki bezkontekstowej dla tego języka. Czy istnieją jakieś systematyczne techniki znajdowania gramatyki bezkontekstowej dla danego języka? Dla stałych języków, …
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.