Pytania otagowane jako regular-languages

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

1
Wnioskowanie o rodzajach uściślenia
W pracy miałem za zadanie wnioskować o pewnych typach informacji o dynamicznym języku. Przepisuję sekwencje instrukcji na letwyrażenia zagnieżdżone , tak jak poniżej: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if …
11 programming-languages  logic  type-theory  type-inference  machine-learning  data-mining  clustering  order-theory  reference-request  information-theory  entropy  algorithms  algorithm-analysis  space-complexity  lower-bounds  formal-languages  computability  formal-grammars  context-free  parsing  complexity-theory  time-complexity  terminology  turing-machines  nondeterminism  programming-languages  semantics  operational-semantics  complexity-theory  time-complexity  complexity-theory  reference-request  turing-machines  machine-models  simulation  graphs  probability-theory  data-structures  terminology  distributed-systems  hash-tables  history  terminology  programming-languages  meta-programming  terminology  formal-grammars  compilers  algorithms  search-algorithms  formal-languages  regular-languages  complexity-theory  satisfiability  sat-solvers  factoring  algorithms  randomized-algorithms  streaming-algorithm  in-place  algorithms  numerical-analysis  regular-languages  automata  finite-automata  regular-expressions  algorithms  data-structures  efficiency  coding-theory  algorithms  graph-theory  reference-request  education  books  formal-languages  context-free  proof-techniques  algorithms  graph-theory  greedy-algorithms  matroids  complexity-theory  graph-theory  np-complete  intuition  complexity-theory  np-complete  traveling-salesman  algorithms  graphs  probabilistic-algorithms  weighted-graphs  data-structures  time-complexity  priority-queues  computability  turing-machines  automata  pushdown-automata  algorithms  graphs  binary-trees  algorithms  algorithm-analysis  spanning-trees  terminology  asymptotics  landau-notation  algorithms  graph-theory  network-flow  terminology  computability  undecidability  rice-theorem  algorithms  data-structures  computational-geometry 
5
Wystarczający i niezbędny warunek dotyczący prawidłowości języka
Które z następujących wyrażeń jest poprawne? istnieją wystarczające i konieczne warunki dotyczące prawidłowości języka, ale jeszcze ich nie odkryto. Nie ma wystarczających i koniecznych warunków dotyczących prawidłowości języka. Pompowanie lematu jest niezbędnym warunkiem nieregularności języka. Pompowanie lematu jest wystarczającym warunkiem nieregularności języka. Wiem, że # (4) jest poprawne, a # …
2
Najmniejszy DFA, który akceptuje podane ciągi i odrzuca inne podane ciągi
Biorąc pod uwagę dwa zbiory ciągów znaków nad alfabetem Σ , czy możemy obliczyć najmniejszy deterministyczny automat skończony (DFA) M taki, że A ⊆ L ( M ) i L ( M ) ⊆ Σ ∗ ∖ BA,BA,BA,BΣΣ\SigmaMMMA⊆L(M)A⊆L(M)A \subseteq L(M)L(M)⊆Σ∗∖BL(M)⊆Σ∗∖BL(M) \subseteq \Sigma^*\setminus B ? Innymi słowy, reprezentuje zestaw pozytywnych przykładów. …
5
Język wartości funkcji afinicznej
Napisz n¯n¯\bar n dla dziesiętnego rozszerzenia nnn (bez wiodącego 0). Niech aaa i bbb będą liczbami całkowitymi o a>0a>0a > 0 . Rozważmy język rozwinięć dziesiętnych wielokrotności plus stałej:aaa M={ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈N}M={ax+b¯∣x∈N}M = \{ \overline{a\,x+b} \mid x\in\mathbb{N} \} Czy MMM regularne? bez kontekstu? (Kontrast z językiem wykresu funkcji afinicznej ) Myślę, że …
5
Czy istnieje znana metoda konstruowania gramatyki przy skończonym zestawie skończonych łańcuchów?
Z mojego czytania wynika, że ​​większość gramatyk dotyczy generowania nieskończonej liczby łańcuchów. Co jeśli pracowałeś na odwrót? Jeśli podano n łańcuchów o długości m, powinno być możliwe stworzenie gramatyki, która wygeneruje te łańcuchy i tylko te łańcuchy. Czy istnieje znana metoda wykonania tego? Idealnie nazwa techniki, którą mogę badać. Alternatywnie, …
3
DFA za akceptację wszystkich ciągów binarnych mocy formy
Możemy utworzyć DFA, przyjmując liczby binarne podzielne przez .nnn Na przykład DFA akceptujący liczby binarne podzielne przez 2 można utworzyć w następujący sposób: Podobnie DFA akceptujący liczby binarne podzielne przez 3 można utworzyć w następujący sposób: Możemy zastosować dobrze zdefiniowaną procedurę, aby utworzyć tego rodzaju DFA. Czy jednak może istnieć …
2
Regularność języków jednoargumentowych o długości słowa suma dwóch resp. trzy kwadraty
Myślę o językach jednoargumentowych LkL.kL_k, gdzie LkL.kL_k jest zbiorem wszystkich słów, których długość jest sumą kkkkwadraty. Formalnie: Lk={an∣n=∑i=1kni2,ni∈N0(1≤i≤k)}L.k={zan∣n=∑ja=1knja2),nja∈N.0(1≤ja≤k)}L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} Łatwo to pokazać L1={an2∣n∈N0}L.1={zan2)∣n∈N.0}L_1=\{a^{n^2}\mid n\in\mathbb{N_0}\}nie jest regularny (np. z Pumping-Lemma). Ponadto wiemy, że każda liczba naturalna jest sumą czterech kwadratów, co implikuje, że dlak≥4k≥4k\ge 4 wszystkie języki LkL.kL_k …
3
Czy regularne?
Kilka tygodni temu podjąłem egzaminy z teorii obliczeń i było to jedno z pytań: Załóżmy, że językL = { (zanbm)r∣ n , m , r ≥ 0 }L.={(zanbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} Czy L jest regularny? Jeśli tak, podaj wyrażenie regularne lub automat. Po tym, jak krótko zapytałem go o odpowiedź …
4
Słowa, które mają ten sam prawy i lewy skojarzony produkt
Zacząłem studiować niedeterministyczne automaty, korzystając z książki Hopcroft i Ullman . Utknąłem w problemie, który uznałem za bardzo interesujący: Daj niedeterministyczny automat skończony akceptujący wszystkie ciągi, które mają tę samą wartość, gdy są oceniane od lewej do prawej, od prawej do lewej, mnożąc zgodnie z poniższą tabelą: ×zabdozazadobbzazadododobza×abcaaacbcabcbca\qquad \displaystyle\begin{array}{c|ccc} \times …
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.