Pytania otagowane jako formal-languages

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

1
Złożoność obliczeniowa a hierarchia Chomsky'ego
Zastanawiam się ogólnie nad związkiem między złożonością obliczeniową a hierarchią Chomsky'ego. W szczególności, jeśli wiem, że jakiś problem jest NP-zupełny, czy wynika z tego, że język tego problemu nie jest pozbawiony kontekstu? Na przykład problem kliki jest NP-zupełny. Czy wynika z tego, że język odpowiadający modelom z klikami ma pewną …
2
Czy język jednoargumentowy jest regularny, jeśli wykładnikiem jest funkcja liniowa?
Wykonując bieżące zadanie dla moich kursów języków formalnych i automatów, w pewnym sensie utknąłem na ćwiczeniach obejmujących języki jednoargumentowe (mam nadzieję, że to właściwy termin), tj. Języki oparte na jednej literze. Nie chcę jednak pytać o konkretne ćwiczenia, ale raczej o bardziej ogólną hipotezę, którą wymyśliłem: Niech i . Moja …
2
Jak słowo „produkcja” stało się synonimem słowa „reguła” w kontekście informatyki?
Studiuję języki formalne i systemy baz produkcyjnych (systemy baz reguł) i jestem trochę zdezorientowany, dlaczego te dwa słowa „produkcja” i „reguła” oznaczają to samo w tak wielu kontekstach w informatyce. W języku angielskim nie wydają się oznaczać tego samego. Nie jestem rodzimym językiem angielskim, ale wiem, że reguła odnosi się …
3
nierozstrzygalny problem i jego negacja jest nierozstrzygalna
Wiele „znanych” nierozstrzygalnych problemów jest jednak co najmniej w połowie nierozstrzygalnych, a ich dopełnienie jest nierozstrzygalne. Jednym z przykładów może być przede wszystkim problem zatrzymania i jego uzupełnienie. Czy ktoś może jednak podać przykład, w którym zarówno problem, jak i jego uzupełnienie są nierozstrzygalne i nierozstrzygalne? Myślałem o języku diagonalizacji …
4
Twierdzenia mostkowe dla teorii grup i języków formalnych
Czy istnieje jakiś naturalny lub znaczący sposób na powiązanie lub połączenie grup matematycznych i języków formalnych CS lub jakieś inne podstawowe pojęcie CS, np. Maszyny Turinga? Szukam referencji / aplikacji. Zauważ jednak, że jestem świadomy związku między półgrupami a językami CS (mianowicie za pośrednictwem automatów skończonych ). (Czy ta literatura …
1
co to jest semantyka?
Istnieje wiele popularnych języków. Ale informatycy mówią nam, że aby zrozumieć zachowanie programów w tych językach, zdecydowanie i jednoznacznie spieramy się na zachowanie programu (np. Udowodnić ich tożsamość), musimy przetłumaczyć je na inny, dobrze zrozumiały język. Nazywają taki język „semantyką”. Autorzy proponują jedną z wielu semantyki. Wyjaśniają znaczenie ich konstrukcji …
1
Czy POSIX BRE może wyrażać wszystkie zwykłe języki?
Wygląda na to, że „podstawowe wyrażenia regularne” zdefiniowane w POSIX.1-2008 nie obsługują naprzemiennego działania a|b(chociaż niektóre implementacje grep rozpoznają wersję ucieczkową \|). Skoro zwykłe języki są z definicji zamknięte w unii, czy to oznacza, że ​​POSIX BRE ma mniejszą moc ekspresji niż automat skończony? Czy jest jakiś sposób na symulację …
4
Dlaczego w Regexach nie ma permutacji? (Nawet jeśli wydaje się, że zwykłe języki to potrafią)
Problem Nie ma łatwego sposobu na uzyskanie permutacji za pomocą wyrażenia regularnego. Permutacja: Uzyskanie słowa („aabc”) w innym porządku, bez zmiany liczby lub rodzaju liter.w=x1…xnw=x1…xnw=x_1…x_n Regex: wyrażenie regularne. Dla weryfikacji: „Permutacje regexów bez powtórzeń” Odpowiedź tworzy kod JavaScript zamiast wyrażenia regularnego, zakładając, że byłoby to prostsze. „Jak znaleźć wszystkie permutacje …
3
Zwykłe języki, których nie można wyrazić za pomocą tylko 2 operacji wyrażenia regularnego
Myślałem, że wszystkie języki regularne można wyrazić za pomocą wyrażeń regularnych (jeśli język jest regularny, można go wyrazić za pomocą wyrażenia regularnego), ale powiedziano mi, że potrzebujesz do tego wszystkich trzech operacji regularnych (konkatenacji, zjednoczenia i gwiazdki) trzymać. Powiedziano mi na przykład, że jeśli mogę korzystać tylko z operacji wyrażenia …
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.