Gramatyka liniowa prawa - ∞ punktów
S->ε
S->1A
S->0S
S->9I
S->3C
S->5E
S->4D
S->2B
S->7G
S->6F
S->8H
F->3K
K->0F
A->2L
K->1G
A->5B
A->0J
B->7A
J->5A
G->6K
G->8S
H->9K
F->5S
K->2H
I->6E
I->5D
J->4S
D->8I
B->6S
K->9B
F->6A
G->9A
K->6L
K->4J
C->1E
L->8K
E->5C
B->4K
C->0D
J->2K
D->2C
A->9F
J->7C
C->6J
C->8L
E->0K
L->0C
B->9C
E->2S
L->6I
I->0L
J->0I
B->2I
I->3B
H->1C
I->7F
C->4H
F->1I
G->4I
I->0G
C->3G
F->8C
D->0A
E->3A
I->9H
A->7D
C->2F
H->7I
A->8E
F->9D
E->8F
A->6C
D->6G
G->0E
D->5F
E->9G
H->2D
D->7H
H->3E
I->2A
K->3I
C->9S
C->7K
E->4B
D->1B
L->1D
J->9E
I->1S
E->1L
J->8D
D->9J
L->2E
J->3L
B->5L
B->8B
L->7J
L->9L
G->1F
A->4A
K->5K
B->3J
H->6H
E->7E
J->1J
D->4E
G->2G
J->6B
D->3D
E->6D
H->4F
I->4C
C->5I
F->0H
H->5G
K->7S
G->3H
L->5H
H->8J
A->3S
H->0B
B->1H
G->7L
K->8A
F->2J
F->7B
L->4G
F->4L
A->1K
B->0G
G->5J
L->3F
Następnie, w zależności od tego, w jaki sposób go „uruchomisz”, wyświetli „tak” lub „nie”.
Nie jest to poważny wpis, tylko trochę zabawy;)
EDYCJA:
Może powinienem trochę wyjaśnić.
Gramatyka jest zbiorem reguł (produkcji), które określają język . Język można traktować jako wszystkie możliwe ciągi utworzone przez alfabet, które odpowiadają regułom jego gramatyki.
Tutaj alfabet jest zbiorem wszystkich cyfr dziesiętnych. Zasady gramatyki mówią, że wszystkie ciągi muszą tworzyć dziesiętne liczby całkowite, które można podzielić przez 13.
Możemy użyć powyższej gramatyki, aby sprawdzić, czy łańcuch należy do naszego języka.
Reguły gramatyki zawierają symbole końcowe (które są elementami w języku), a także symbole nieterminalne, które są zastępowane rekurencyjnie.
Łatwiej jest wyjaśnić, co się dzieje na przykładzie:
Powiedzmy na przykład, że testowany przez nas ciąg to 71955.
Zawsze występuje symbol początkowy (który nie jest końcowy), w przypadku gramatyki powyżej jest to „S”. W tym momencie nie odczytaliśmy żadnych znaków z naszego ciągu:
current pattern symbol read
S ε
Teraz czytamy pierwszy symbol w naszym ciągu, który jest „7”, a następnie szukamy reguły w gramatyce, która ma dowolny z nieterminali w naszym bieżącym wzorze po lewej stronie „->” i że ma nasz symbol po prawej stronie „->”. Na szczęście jest jeden (S-> 7G), więc zastępujemy nieterminalne symbole w naszym obecnym wzorze prawą stroną nowej reguły:
current pattern symbol read
7G 7
Teraz mamy wzorzec nieterminalny „G”, a następnym symbolem do odczytania jest „1”, więc szukamy reguły w naszej gramatyce, która zaczyna się od „G-> 1”. (G-> 1F), więc zastępujemy terminale RHS naszej nowej reguły:
current pattern symbol read
71F 1
Powtarzaj ten proces:
Następna zasada: F-> 9D
current pattern symbol read
719D 9
Następna zasada: D-> 5F
current pattern symbol read
7195F 5
Następna zasada: F-> 5S
current pattern symbol read
71955S 5
W tym momencie nie mamy już żadnych symboli w naszym ciągu, ale mamy tam inny symbol nieterminalny. Widzimy z pierwszej reguły gramatyki, że możemy zastąpić „S” pustym ciągiem (ε): S-> ε
W ten sposób otrzymujemy aktualny wzór: 71955ε, co odpowiada 71955.
Przeczytaliśmy wszystkie symbole w naszym ciągu, a wzorzec nie zawiera żadnych symboli nieterminalnych. Co oznacza, że ciąg należy do języka, a zatem 71955 jest w rzeczywistości podzielny przez 13.
Tj. Celem jest mieć wzór = ciąg. Jeśli masz jakieś nieterminalne symbole, po przeczytaniu wszystkich symboli w łańcuchu, łańcuch nie należy do języka. Podobnie, jeśli nadal masz więcej symboli do przeczytania, ale w gramatyce nie ma żadnych reguł, które pozwolą ci iść naprzód, to łańcuch nie należy do języka.