|
Struktura danych | Napis (ciąg znaków) |
Złożoność |
Czasowa | |
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.
Algorytm
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
- 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
- Słowo należy do języka, jeśli gdzie to symbol startowy gramatyki
Przykład
Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky’ego:
- [1]
- [2]
- [3]
- [4]
- [5]
Formalnie:
Pytanie: ?
Inicjalizacja tabeli:
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 | | | | | |
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
| 1 | 2 | 3 | 4 | 5 |
| a | a | b | b | b |
---|
1 | | | | | |
2 | – | | | |
3 | | | |
4 | | |
5 | |
- pole z racji produkcji [3]
| 1 | 2 | 3 | 4 | 5 |
| a | a | b | b | b |
---|
1 | | | | | |
2 | – | | | |
3 | | | |
4 | | |
5 | |
- pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
| 1 | 2 | 3 | 4 | 5 |
| a | a | b | b | b |
---|
1 | | | | | |
2 | – | | – | |
3 | | | |
4 | | |
5 | |
- pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
| 1 | 2 | 3 | 4 | 5 |
| a | a | b | b | b |
---|
1 | | | | | |
2 | – | | – | – |
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
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | | 4 | | | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | | 4 | | | 5 | |
|
- pole z racji reguły
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | – | | 4 | | | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | | 4 | | | 5 | |
|
- pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | | 5 | |
|
Wyrazy długości 4:
- pole z racji reguły
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | – | | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | – | | 5 | |
|
- pole ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol lub ciąg symboli nieterminalnych
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | |
|
Wyrazy długości 5:
- pole z racji reguły
| 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | – |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | – |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | – |
| | 1 | 2 | 3 | 4 | 5 | | a | a | b | b | b |
---|
1 | | | | | | 2 | – | | – | – | 3 | – | | – | 4 | | – | 5 | |
|
Ponieważ symbol startowy nie jest podzbiorem zbioru w polu czyli wyraz nie jest elementem gramatyki
Zobacz też
Bibliografia
- John E. Hopcroft: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005, s. 276. ISBN 83-01-14502-1.