Pytania otagowane jako formal-grammars

Pytania dotyczące gramatyki formalnej, generatywne opisy języków formalnych.

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
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 …
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ę …
5
Czym różni się brak jednoznaczności od determinizmu?
Próbuję zrozumieć, co należy rozumieć przez „deterministyczny” w wyrażeniach takich jak „deterministyczna gramatyka bezkontekstowa”. (W tej dziedzinie są bardziej deterministyczne „rzeczy”). Byłbym wdzięczny za przykład bardziej niż najbardziej wyszukane wyjaśnienie! Jeśli to możliwe. Moje główne źródło zamieszania polega na tym, że nie jestem w stanie powiedzieć, w jaki sposób ta …
1
Różnica między wyrażeniem regularnym a gramatyką w automatach
Jestem nowy w automatach. Krótkie wprowadzenie do wyrażeń regularnych otrzymałem wczoraj. Przeczytałem różne reguły definiujące wyrażenie regularne. Ale nie jestem w stanie odróżnić wyrażeń regularnych od gramatyki języka (nie uczono mnie gramatyki wyrażeń regularnych). Rozumiem, że gramatyka pomaga nam generować poprawne ciągi w języku, ale wtedy właśnie takie są reguły …
3
Znaczenie normalnych form, takich jak normalna forma Chomsky'ego dla CFG
Rozumiem, że gramatyki bezkontekstowe mogą być używane do reprezentowania języków bezkontekstowych. Mogą być niejasne. Mamy również normalne formy, takie jak normalna postać Chomsky'ego i Greibacha . Nie mogłem zrozumieć takiej potrzeby. Dlaczego są ważne w teorii języków? Wszystkie podręczniki, o których mówiłem, mówią o tych normalnych formach, ale nie mówią …
2
Czy wszystkie języki kontekstowe są rozstrzygalne?
Przeglądałem definicję języka kontekstowego w Wikipedii i znalazłem to: Każda kategoria języków jest odpowiednim podzbiorem kategorii bezpośrednio nad nią. Każdy automat i gramatyka w każdej kategorii ma równoważny automat lub gramatykę w kategorii bezpośrednio nad nią. Widziałem, że automat ograniczany liniowo jest bezpośrednio poniżej decydującego w porządku tego artykułu. Jeśli …
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.