Algorytm CYK (Cocke’a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky’ego. Algorytm działa w czasie
gdzie
jest długością słowa, a
jest rozmiarem gramatyki.
Pseudokod algorytmu:
- Tworzymy tablicę
dla
zaś
przebiega wszystkie nieterminale (czy też równoważnie ich numery), wszystkie jej wartości ustawiając na 0
- Dla każdego znaku
na pozycji
i dla każdego
takiego, że w gramatyce jest produkcja
ustawiamy w tablicy ![{\displaystyle T[i,1,X]:=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2a121ea944edc80b56feae1d61f1fb797d46411)
- Dla każdej długości
od 2 do
- Dla każdego początku
od 1 do
- Dla każdego podziału
od 1 do
- Jeśli w tablicy są ustawione
i
a w gramatyce mamy produkcję
ustawiamy ![{\displaystyle T[j,i,Z]:=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37faad27c09b12c93f689616b6949c6710ca08a3)
- Słowo należy do języka, jeśli
gdzie
to symbol startowy gramatyki
Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky’ego:
- [1]
![{\displaystyle S\to AC}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caf71c49987df93273e776adb4a369440c5a9e82)
- [2]
![{\displaystyle C\to SB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6bd9401c8adf11d23526fa006f0d6feceafb22e7)
- [3]
![{\displaystyle S\to AB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/49c345d708e77280fd02a6ee6e0bf0497a4a2a3a)
- [4]
![{\displaystyle A\to a}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e688e0ef43916770fa1fd1275386427d815966a)
- [5]
![{\displaystyle B\to b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/413ac2f0929d01e98f9f30d01636e04adc421306)
Formalnie:
![{\displaystyle G=\{a^{n}b^{n}|n\geqslant 1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/17b98f4c3db5373afd853e275761d664b5f4eb9c)
Pytanie:
?
Inicjalizacja tabeli:
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
|
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 1:
- pola
z racji istnienia reguły [4]
- pola
z racji istnienia reguły [5]
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
|
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 2:
- pole
ponieważ nie istnieje żadne reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ![{\displaystyle AA}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c4bbbeba3c9275c1b8612ed282f8f1347c9629b)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
z racji produkcji [3]
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
|
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ![{\displaystyle BB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f58e28c8465f8b93b870d374f0b92986e5a93934)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ![{\displaystyle BB}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f58e28c8465f8b93b870d374f0b92986e5a93934)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 3:
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
lub tylko ![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
|
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
|
|
4 |
|
|
5 |
|
|
- pole
z racji reguły ![{\displaystyle [2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa32363c093f4cfd50ecba68068bcfd396ea8bff)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
– |
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
|
4 |
|
|
5 |
|
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol ![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
|
|
5 |
|
|
Wyrazy długości 4:
- pole
z racji reguły ![{\displaystyle [1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
– |
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
– |
|
5 |
|
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol
lub ciąg symboli nieterminalnych ![{\displaystyle CB.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ec86b17142b1b140b8251021a3d0e5d70a52b62a)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
|
|
Wyrazy długości 5:
- pole
z racji reguły ![{\displaystyle [2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa32363c093f4cfd50ecba68068bcfd396ea8bff)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{A\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c72ff6b32e6b20b370a6da3d6918a463012e8377) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
![{\displaystyle \{B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/37a32e0f2898eeb228edeeaaf3673631790e9d9d) |
|
2 |
– |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
– |
–
|
3 |
– |
![{\displaystyle \{C\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5c25b171beb88f274366556a866810394cc3e713) |
–
|
4 |
![{\displaystyle \{S\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c538e8a627736d22bbe813ea1682488589378774) |
–
|
5 |
|
|
Ponieważ symbol startowy
nie jest podzbiorem zbioru w polu
czyli
wyraz
nie jest elementem gramatyki