Etiket Arşivleri: Chomsky normal form (CNF)

Context Free grammar (CFG) to Chomsky normal form (CNF) conversion

CFG’ler CNF’ye dönüştürülebilmektedir. Bir CFG’nin CNF’ye uygun olabilmesi için A->a A->BC S->e(epsilon) şeklinde ifade edilebilmesi gerekmektedir. Buradan çıkarılabilecek kurallar: -null/e(epsilon) ifadeler olmayacak -Bire bir A->B, B->C, C->D gibi nonterminal geçişleri olmayacak -terminal ve non-terminal semboller yan yana olmayacak -Üç sembollü herhangi bir ifade olmayacak. Yani A->BCD gibi. 1.Örnek: 2.Örnek: