Pytania otagowane jako regular-expressions

Pytania o wyrażenia regularne, formalizm opisu języków regularnych.

3
Jak utworzyć DFA z wyrażenia regularnego bez użycia NFA?
Celem jest utworzenie DFA z wyrażenia regularnego, a użycie opcji „Regular exp> NFA> Konwersja DFA” nie jest opcją. Jak należy to zrobić? Zadałem to pytanie naszemu profesorowi, ale powiedział mi, że możemy korzystać z intuicji i uprzejmie odmówił podania jakichkolwiek wyjaśnień. Więc chciałem cię zapytać. Opcja „Regular exp> NFA> Konwersja …
2
Czy język wyrażeń regularnych wymaga automatycznych mechanizmów wypychania w celu jego parsowania?
Chcę przekonwertować wprowadzone przez użytkownika wyrażenie regularne na NFA, aby móc następnie uruchomić NFA dla łańcucha w celu dopasowania. Jakiej minimalnej maszyny można użyć do parsowania wyrażeń regularnych? Zakładam, że musi to być automat push, ponieważ obecność nawiasów oznacza konieczność liczenia, a DFA / NFA nie może wykonać dowolnego liczenia. …
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
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 
3
Jak przekonwertować NFA z nakładającymi się cyklami na wyrażenie regularne?
Jeśli dobrze rozumiem, NFA mają taką samą moc ekspresji jak wyrażenia regularne. Często odczytywanie równoważnych wyrażeń regularnych z NFA jest łatwe: przekładasz cykle na gwiazdy, skrzyżowania jako alternatywy i tak dalej. Ale co zrobić w tym przypadku: [ źródło ] Nakładające się cykle utrudniają zobaczenie, co akceptuje ten automat (pod …
1
Konstruujesz wszystkie języki bezkontekstowe z zestawu języków podstawowych i właściwości zamknięcia?
Jednym ze sposobów patrzenia na wyrażenia regularne jest konstruktywny dowód na następujący fakt: możliwe jest zbudowanie języków regularnych, zaczynając od małego zestawu języków i łącząc je za pomocą małego, stałego zestawu właściwości zamknięcia. W szczególności, jeśli zaczniemy od pustego języka, języka zawierającego pusty ciąg i języków wszystkich ciągów jednoznakowych, możemy …
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ć …
1
Kiedy wyrażenie regularne nie jest wyrażeniem regularnym?
Ponieważ studiuję na kursie języka formalnego, natknąłem się na te fascynujące posty ( One Two ), które opisują, jak znaleźć liczbę pierwszą za pomocą wyrażenia regularnego . Jak już powiedziałem, regexp , a nie wyrażenie regularne . Ponieważ wyrażenie regularne może pasować do ciągów obliczanych przez automat skończony i znalezienie …
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ź …
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.