Pytania otagowane jako formal-languages

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

1
Potwierdzenie zamknięcia w zamian języków akceptowanych przez automaty min-heap
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu …
3
Język nieskończony a język skończony
Nie jestem pewien, czy w teorii komputerowej używa się zwrotów „nieskończony” język lub „skończony” język. Myślę, że źródłem problemu jest to, że język taki jak jest nieskończony w tym sensie, że może wygenerować nieskończoną (ale policzalną) liczbę łańcuchów. Jednak nadal może być rozpoznany przez automat skończony .L = { a …
3
Znalezienie przykładów języków „antypalindromicznych”
Niech Σ={0,1}Σ={0,1}\Sigma = \{ 0, 1 \} . Język mówi się, że „anty-palindrom” własność jeśli każdy ciąg że jest palindrom, . Ponadto dla każdego łańcucha który nie jest palindromem, lub , ale nie oba (!) (Wyłączne lub).L⊆Σ∗L⊆Σ∗L \subseteq \Sigma^* wwww∉Lw∉Lw\notin Luuuu∈Lu∈Lu\in LReverse(u)∈LReverse(u)∈L\mathrm{Reverse}(u) \in L Rozumiem właściwość anty-palindromową, ale nie mogłem …
2
Operacja gwiazdy Kleene na pustym języku
W moim podręczniku wspomniano, że: gdzie to pusty język.∅∅∗={ϵ}∅∗={ϵ}\emptyset^*=\{\epsilon\}∅∅\emptyset Wiemy jednak, że , gdzie to dowolny język.L⋅∅=∅L⋅∅=∅L \cdot \emptyset = \emptysetLLL Nie jestem w stanie intuicyjnie zrozumieć tej koncepcji, ponieważ operacja gwiazdy Kleene wskazuje na fakt, że .∅∗=∅0∪∅1∪∅2∪⋯∅∗=∅0∪∅1∪∅2∪⋯\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots Dlaczego więc nie jest równe ?∅∗∅∗\emptyset^*∅∅\emptyset
1
Moc obliczeniowa deterministycznych versus niedeterministycznych automatów typu min-heap
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu …
2
Liczba słów o określonej długości w zwykłym języku
Czy istnieje algebraiczna charakterystyka liczby słów o danej długości w zwykłym języku? Wikipedia podaje wynik nieco nieprecyzyjnie: Dla każdego języka regularnego istnieje stałych i wielomiany tak, że dla każdego numer z słowa o długości w spełnia równanie .LLLλ1,…,λkλ1,…,λk\lambda_1,\,\ldots,\,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\,\ldots,\,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLLsL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkns_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n Nie jest określone, w jakiej przestrzeni żyje ( , jak przypuszczam) i …
2
Zdecydowane języki niewrażliwe na kontekst
Można argumentować, że większość języków stworzonych do opisywania codziennych problemów ma charakter kontekstowy. Z drugiej strony jest możliwe i nietrudno znaleźć niektóre języki, które nie są rekurencyjne, a nawet nie są wymienne. Pomiędzy tymi dwoma typami znajdują się rekurencyjne języki beztekstowe. Wikipedia podaje tutaj jeden przykład : Przykładem języka rekurencyjnego, …
2
Jest uzupełnieniem {ww | …} Bez kontekstu?
Zdefiniuj język jako . Innymi słowy, zawiera słowa, których nie można wyrazić jako jakieś słowo powtórzone dwukrotnie. Czy bezkontekstowy czy nie?LLLL={a,b}∗−{ww∣w∈{a,b}∗}L={a,b}∗−{ww∣w∈{a,b}∗}L = \{a, b\}^* - \{ww\mid w \in \{a, b\}^*\}LLLLLL Próbowałem przeciąć z , ale nadal nie mogę niczego udowodnić. Spojrzałem również na twierdzenie Parikha, ale to nie pomaga.LLLa∗b∗a∗b∗a∗b∗a∗b∗a^*b^*a^*b^*
2
Jakie jest pochodzenie λ dla pustego łańcucha?
Zazwyczaj używam symbolu dla pustego łańcucha (pusty wyraz lub łańcuch pusty). Ale wiem, że niektórzy ludzie używają λ zamiast ε .εε\varepsilonλλ\lambdaεε\varepsilon Myślę, że pochodzi od słowa „pusty”. Jednak nie wiem, skąd się bierze λ .εε\varepsilonλλ\lambda W teorii automatów istnieje przejście epsilon na automatach, a także mówi się, że jest to …
2
Co to jest parser IELR (1)?
Próbuję nauczyć się używania żubra. Bizon manpage (1) mówi o bizonie: Wygeneruj deterministyczny analizator składni LR lub uogólniony analizator składni LR (GLR), korzystając z tabel analizatora składni LALR (1), IELR (1) lub kanonicznej LR (1). Co to jest parser IELR? Wszystkie istotne artykuły, które znalazłem w sieci WWW, są płatne.
1
Kiedy
Zgodnie z artykułem Wikipedii , L w oznacza „skanowanie od lewej do prawej”, a „R” oznacza „pochodzenie od prawej”. Jednak w oryginalnym artykule Knutha na temat gramatyki definiuje (na stronie 610) jako język, który jest „możliwy do przetłumaczenia z lewej na prawą za pomocą związanego ”.L R ( k )L.R(k)LR(k)L …
2
Czy zestawy przed i po dla gramatyk bezkontekstowych zawsze są pozbawione kontekstu?
Niech GGG będzie gramatyką bezkontekstową. Łańcuch zacisków i nieterminali z GGG mówi się zdań tworzą z GGG , czy można go otrzymać stosując produkcje GGG zero lub więcej razy symbolu startu SSS . Niech SF(G)SF⁡(G)\operatorname{SF}(G) będzie zbiorem form zdaniowych GGG . Niech α∈SF(G)α∈SF⁡(G)\alpha \in \operatorname{SF}(G) i pozwolić ββ\beta być podłańcuchem …
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.