Ĉu ni povas determini ĉu donita ĉeno estas akceptita de senkunteksta gramatiko? Ĉu ĉi tiu problemo estas decidebla?
Determini ĉu antaŭfiksita ŝnuro estas akceptita per senkunteksta gramatiko estas fundamenta problemo en komputila komplekseca teorio. Tiu problemo kategoriiĝas sub la pli larĝa kategorio de decideblo, kiu traktas determini ĉu speciala posedaĵo validas por antaŭfiksita enigaĵo. Okaze de senkuntekstaj gramatikoj, la problemo de ĉenakcepto estas ja decidebla.
Senkunteksta gramatiko estas formala sistemo konsistanta el aro de produktadaj reguloj, kiuj priskribas kiel generi ŝnurojn en lingvo. Ĝi estas difinita per opo (V, Σ, R, S), kie V estas aro de nefinaj simboloj, Σ estas aro de finaj simboloj, R estas aro de produktadreguloj, kaj S estas la komenca simbolo. La lingvo generita de senkunteksta gramatiko estas la aro de ĉiuj ĉenoj, kiuj povas esti derivitaj de la komenca simbolo uzante la produktadregulojn.
Por determini ĉu antaŭfiksita ĉeno estas akceptita per senkunteksta gramatiko, ni povas uzi diversajn algoritmojn, kiel la CYK-algoritmo aŭ la Earley-algoritmo. Tiuj algoritmoj utiligas dinamikajn programajn teknikojn por efike kontroli ĉu ŝnuro povas esti derivita de la komenca simbolo de la gramatiko.
La CYK-algoritmo, ekzemple, konstruas tabelon kie ĉiu ĉelo reprezentas subŝnuron de la eniga ĉeno kaj aron de ne-terminaloj kiuj povas generi tiun subĉenon. Ripete plenigante la tabelon bazitan sur la produktadreguloj de la gramatiko, la algoritmo determinas ĉu la komenca simbolo povas generi la tutan enigŝnuron. Se la komenca simbolo aperas en la supra dekstra ĉelo de la tabelo, tiam la ĉeno estas akceptita de la gramatiko; alie, ĝi ne estas.
Konsideru la sekvan ekzemplon: Ni diru, ke ni havas senkuntekstan gramatikon kun la produktadaj reguloj:
S -> AB
A -> a
B -> b
Se ni volas determini ĉu la ĉeno "ab" estas akceptita de ĉi tiu gramatiko, ni povas apliki la CYK-algoritmon. La algoritmo konstruas tabelon kun du ĉeloj, unu por ĉiu signo en la eniga ĉeno. La tabelo aspektas jene:
| 1 | 2 |
—+—+—+
1 | A | S |
—+—+—+
2 | | B |
—+—+—+
Komencante de la malsupra vico, ni povas vidi ke la ĉelo (2,2) enhavas la ne-finan B, kiu estas generita per la produktadregulo B -> b. Movante supren al la supra vico, ni trovas ke la ĉelo (1,2) enhavas la ne-finan S, kiu estas generita per la produktadregulo S -> AB. Fine, la ĉelo (1,1) enhavas la ne-finaĵon A, kiu estas generita per la produktadregulo A -> a. Ĉar la komenca simbolo S aperas en la supra dekstra ĉelo, ni povas konkludi ke la ĉeno "ab" estas akceptita de la gramatiko.
La problemo de determini ĉu antaŭfiksita ĉeno estas akceptita de senkunteksta gramatiko estas decidebla. Algoritmoj kiel ekzemple la CYK-algoritmo aŭ la Earley-algoritmo povas esti uzitaj por efike kontroli ĉu ĉeno povas esti derivita de la komenca simbolo de la gramatiko. Tiuj algoritmoj utiligas dinamikajn programajn teknikojn por konstrui tabelojn kaj determini la akcepton de la ŝnuro.
Aliaj lastatempaj demandoj kaj respondoj pri Decideblo:
- Ĉu bendo povas esti limigita al la grandeco de la enigaĵo (kiu estas ekvivalenta al la kapo de la turingmaŝino estanta limigita por moviĝi preter la enigaĵo de la TM-bendo)?
- Kion signifas, ke malsamaj varioj de Turing-Maŝinoj estas ekvivalentaj en komputadkapablo?
- Ĉu turing rekonebla lingvo povas formi subaron de decidebla lingvo?
- Ĉu la halta problemo de Turing-maŝino estas decidebla?
- Se ni havas du TM-ojn, kiuj priskribas decideblan lingvon, ĉu la ekvivalenta demando estas ankoraŭ nedecidebla?
- Kiel la akceptproblemo por liniaj baritaj aŭtomatoj diferencas de tiu de Turing-maŝinoj?
- Donu ekzemplon de problemo kiu povas esti decidita per lineara barita aŭtomato.
- Klarigu la koncepton de decideblo en la kunteksto de liniaj baritaj aŭtomatoj.
- Kiel la grandeco de la bendo en liniaj baritaj aŭtomatoj influas la nombron da apartaj konfiguracioj?
- Kio estas la ĉefa diferenco inter liniaj baritaj aŭtomatoj kaj Turing-maŝinoj?
Vidu pliajn demandojn kaj respondojn en Decidebleco