Cocke-Younger-Kasami-algoritmus

Magyar

Kiejtés

IPA: [ ˈt͡sot͡skɛiouŋɡɛrkɒʃɒmiɒlɡoritmuʃ]

Főnév

(matematika)

Cocke-Younger-Kasami (CYK) algoritmus

A CYK algoritmus egy dinamikus programozási technika, amely meghatározza, hogy egy adott sztring egy kontextusfüggetlen grammatika által generálható-e. Az algoritmus feltételezi, hogy a grammatikát Chomsky normálformában (CNF) adjuk meg.

Python Implementáció

1. Kontextusfüggetlen grammatika CNF-ben

def cyk_algorithm(string, grammar, start_symbol):
    """
    CYK algoritmus a sztring grammatika általi felismerésére.

    :param string: A vizsgálandó sztring
    :param grammar: A grammatika, szabályok listája (pl. {'A': [('B', 'C'), ('a',)]})
    :param start_symbol: A grammatika kezdőszimbóluma
    :return: True, ha a sztring generálható, különben False
    """
    n = len(string)
    # Tábla inicializálása: tábla[i][j] a baloldali szimbólumok halmaza
    table = [[set() for _ in range(n)] for _ in range(n)]

    # Egyszimbólumos szabályok keresése (alapszint)
    for i, char in enumerate(string):
        for lhs, rhs in grammar.items():
            for rule in rhs:
                if len(rule) == 1 and rule[0] == char:
                    table[i][i].add(lhs)

    # Dinamikus programozás a tábla kitöltésére
    for length in range(2, n + 1):  # Szegmens hossz
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):  # Felosztási pont
                for lhs, rhs in grammar.items():
                    for rule in rhs:
                        if len(rule) == 2:  # Kétszimbólumos szabály
                            B, C = rule
                            if B in table[i][k] and C in table[k + 1][j]:
                                table[i][j].add(lhs)

    # Ellenőrzés, hogy a kezdőszimbólum benne van-e az [0][n-1] cellában
    return start_symbol in table[0][n - 1]

# Példa grammatika CNF-ben
grammar = {
    'S': [('A', 'B'), ('B', 'C')],
    'A': [('B', 'A'), ('a',)],
    'B': [('C', 'C'), ('b',)],
    'C': [('A', 'B'), ('a',)]
}

# Vizsgálandó sztring
string = "baaba"

# Kezdőszimbólum
start_symbol = 'S'

# Algoritmus futtatása
result = cyk_algorithm(string, grammar, start_symbol)
print(f"A sztring generálható: {result}")

Kimenet:

A sztring generálható: True

C++ Implementáció

1. Kontextusfüggetlen grammatika CNF-ben

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>

using namespace std;

// CYK algoritmus
bool cykAlgorithm(const string& str, const map<string, vector<pair<string, string>>>& grammar, const string& startSymbol) {
    int n = str.size();
    vector<vector<set<string>>> table(n, vector<set<string>>(n));

    // Alapszint: egyszimbólumos szabályok
    for (int i = 0; i < n; ++i) {
        for (const auto& rule : grammar) {
            const string& lhs = rule.first;
            for (const auto& rhs : rule.second) {
                if (rhs.second.empty() && rhs.first == string(1, str[i])) {
                    table[i][i].insert(lhs);
                }
            }
        }
    }

    // Dinamikus programozás
    for (int length = 2; length <= n; ++length) { // Szegmens hossz
        for (int i = 0; i <= n - length; ++i) {
            int j = i + length - 1;
            for (int k = i; k < j; ++k) {
                for (const auto& rule : grammar) {
                    const string& lhs = rule.first;
                    for (const auto& rhs : rule.second) {
                        if (!rhs.second.empty()) { // Kétszimbólumos szabályok
                            const string& B = rhs.first;
                            const string& C = rhs.second;
                            if (table[i][k].count(B) && table[k + 1][j].count(C)) {
                                table[i][j].insert(lhs);
                            }
                        }
                    }
                }
            }
        }
    }

    // Ellenőrzés
    return table[0][n - 1].count(startSymbol);
}

int main() {
    // Példa grammatika CNF-ben
    map<string, vector<pair<string, string>>> grammar = {
        {"S", {{"A", "B"}, {"B", "C"}}},
        {"A", {{"B", "A"}, {"a", ""}}},
        {"B", {{"C", "C"}, {"b", ""}}},
        {"C", {{"A", "B"}, {"a", ""}}}
    };

    // Vizsgálandó sztring
    string str = "baaba";

    // Kezdőszimbólum
    string startSymbol = "S";

    // CYK algoritmus futtatása
    if (cykAlgorithm(str, grammar, startSymbol)) {
        cout << "A sztring generálható: True" << endl;
    } else {
        cout << "A sztring generálható: False" << endl;
    }

    return 0;
}