Kui aga ekvivalentsiklass sisaldab keele sõna, siis kuulub sellesse ekvivalentsiklassi terve keel (xe kuulub keelde ja ye kuulub keelde). Klassist Ck sagu lõppolek. Kui x ja y kuuluvad ühte ekvivalentsiklassi, siis kuuluvad sinna ka terminaali a korral xa ja ya. Automaati lisame iga oleku Ci ja iga terminaali a jaoks kaare olekusse Cj. Nii tagame, et (w,C0) * (e,Ck) mis tähendab, et automaat aktsepteerib keele mis omakorda tähendab, et keel on regulaarne. 13. KV-keelte süntaksi- ja tuletuspuud. Süntaksipuu: Iga järjestatud puu T = (A,R), mille tippude märgendus on antud kujutusega f, on esitatav termina: · kui tipp a on terminaalne tipp, siis märgend M = f(a) on term · kui tipp a on mitteterminaalne tipp märgendiga M = f(a), mille vahetuid alampuid vasakult paremale tähistavad termid t1 .. tn, siis avaldis M(t1,..,tn) on term, mis tähistab puu T alampuud juurega a Idee poolest sama on lrep(T) asendame lihtsalt tipud neile vastavate märgenditega.
DEF: KV-keel L on ühene, kui kui leidub ühene KV-grammatika G , nii et L = L(G). Teoreem: Olgu L1 ja L2 ühesed keeled. Kui L1 ∩ L2 = ∅, siis on keel L1 ∪ L2 samuti ühene. T: Oletame, et L1-l ja L2-l on ühisosa. Keeled L2 = {anbncm | n,m > 0} ja L3 = {ambncn | n, m > 0} on ühesed, grammatikad on {S→AB, A→aAb, A→ab, B →cB, B →c} ja {S →AB, A→aA, A→a, B →bBc, B →bc}. Keel L = {anbncm | n,m > 0} ∪ {ambncn | n,m > 0} on mitmene, sest saab mitu tuletuspuud teha. 9 KV grammatika Chomsky normaalkuju. DEF: KV gramaatika G = (N,Σ,P,S) on Chomsky normaalkujul, kui tema produktsioonid on ühel kujudest: 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 → ε
annaabi.ee 
