"mitteterminaale" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

A→BC; A→a(terminaal); S(lähtesümbol)→ε. 
 Teoreem: Iga KV keel on genereeritav KV grammatikaga Chomsky normaalkujul. T: 1)lisame uue algsümboli S0 ja produktisooni S0 → S (nüüd ükski parem pool ei sisalda lähtesümbolit) 2) kaotame kõik A → ε. Kui T → Aa ja A → ε, siis kustutame A → ε ja lisame T → a (sama mis T → εa) 3) kaotame kõik A → B. Kui T → A ja A → a, siis asendame T → A kohe produktsiooniga T → a. 4) sobitame muud reeglid, kasutades abi-mitteterminaale. Nt S→aTb muudame S→AC, lisame A→a, C→TB, B→b. 10 KV-keelte süntaksanalüüsi ülesanne. CKY-algoritm. Cocke-Kasami-Younge’i algoritmi abil saame teada, kas sõne kuulub KV keelde L. antud: KV grammatika Chomsky normaalkujul ja sõne w=w1…wn tulemus: accept, kui w selle grammatikaga keelde. Else, reject. tehakse püramiidikujuline tabel, mille alumisse ritta pannakse etteantud sõne kõik osad ja igasse tabeli lahtrisse kuidas neid kombinatsioone saada