Wskazówki dotyczące tworzenia " gramatyki bez kontekstu"
Jestem nowy w CFG,
Czy ktoś może mi dać wskazówki w tworzeniu CFG, które generuje jakiś język
Na przykład
L = {am bn | m >= n}
To co mam to:
So -> a | aSo | aS1 | eS1 -> b | bS1 | e
Ale myślę, że ten obszar jest zły, ponieważ jest szansa, że liczba b's może być większa niż a's.
4 answers
Jak napisać CFG na przykładzie ambn
L = {a m b n | m > = n}.
Opis języka: a m b n składają się z a następnie b gdzie a są równe lub większe niż liczba b.
Niektóre przykładowe ciągi znaków: {^, a, aa, aab, aabb, aaaab, ab......}
Więc zawsze jest jeden a for one b ale extra a są możliwe. infect string może składać się z a tylko. Również zauważyć ^ null jest członkiem języka, ponieważ w ^ NumberOf(a) = NumberOf(b) = 0
Jak napisać gramatykę akceptującą język utworzony przez ciągi a m b n ?
W gramatyce powinny być takie zasady, że jeśli dodasz b symbol dodajesz również a symbol.
I można to zrobić za pomocą coś w stylu:
S --> aSb
Ale jest to niekompletne, ponieważ potrzebujemy reguły, aby wygenerować dodatkowe a s:
A --> aA | a
Połącz dwie reguły produkcji w jedną gramatykę CFG.
S --> aSb | A
A --> aA | a
Więc możesz wygenerować dowolny ciąg znaków, który składa się z a również a oraz b in (am bn) wzór.
Ale w powyższej gramatyce nie ma sposobu na wygenerowanie ^ sznurek.
Więc, zmień tę gramatykę tak:
S --> B | ^
B --> aBb | A
A --> aA | a
Ta gramatyka może generować {a m b n | m >= n} język.
Uwaga : aby wygenerować ^ null string, dodałem dodatkowy pierwszy krok w gramatyce, dodając S--> B | ^, więc możesz dodać ^ lub twój ciąg symbolu a oraz b. (teraz B odgrywa rolę S z poprzedniej gramatyki, aby wygenerować równe liczby a oraz b)
Edit: Thanks to @ Andy Hayden
Możesz również napisać gramatykę równoważną dla tego samego języka {a m b n / m >= n}:
S --> aSb | A
A --> aA | ^
Uwaga: tutaj A --> aA | ^ można wygenerować zero lub dowolną liczbę a. I to powinno być lepsze od mojej gramatyki, ponieważ generuje mniejsze drzewo parsowania dla tego samego ciągu.
(mniejsza wysokość preferowana ze względu na efektywne parsowanie )
Następujące wskazówki mogą być Język Polski jest językiem ojczystym dla 3,5%, Angielski dla 3,5% mieszkańców (2011).]}
- masz być jasne o języku, że to, co opisuje (znaczenie / wzór).
- możesz zapamiętać rozwiązania kilku podstawowych problemów (chodzi o to, że możesz pisać nowe gramatyki).
- możesz pisać Zasady dla podstawowych języków, takich jak napisałem dla RE w tym przykładzie, aby napisać Right-Linear-Grammmar . Zasady pomogą Ci napisać gramatykę dla nowych języków.
- innym podejściem jest najpierw narysowanie automatów , a następnie konwersja automatów na gramatykę. Mamy predefiniowane techniki pisania gramatyki z automatów z dowolnej klasy języka formalnego.
- jak dobry programista, który uczy się czytając kod innych, podobnie można nauczyć się pisać gramatyki dla języków formalnych.
również gramatyka, którą napisałeś, jest błędna.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-05-23 11:47:14
Chcesz utworzyć gramatykę dla następującego języka
L= {an bm | m>=n }
Oznacza to, że liczba " b "powinna być większa lub równa niż liczba "a" albo można powiedzieć, że dla każdego " b "może być co najwyżej jedno "a". nie odwrotnie.
Oto Gramatyka dla tego języka
S-> aSb | Sb | b | ab
W tej gramatyce dla każdego "a" jest jedno "b". ale b można wygenerować bez generowania żadnego "a".
Możesz również wypróbować te języki:
L1= {an bm | m > n }
L2= {an bm | m >= 2n }
L3= {an bm | 2m >= n }
L4= {an bm | m != n }
Daję gramatykę dla każdego język.
Dla L1
S-> aSb | Sb | b
Dla L2
S-> aSbb | Sb | abb
Dla L3
S-> AASb | Sb | aab | ab | b
Dla L4
S-> S1 | S2
S1-> aS1b | S1b | b
S2-> aS2b | aS2 | a
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-26 15:53:39
Najmniejsze zmienne: S - > a S b | a S | e
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-02-18 18:00:19
Z mniejszymi zmiennymi:
S - > a S b / A S | A b | E
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2014-04-07 15:48:57