Open AccessAlternative Vidhi to Conversion of Cyclic CNF->GNF
Author(s) -
Avinash Bansal
Publication year - 2012
Publication title -
international journal of computer and technology
Language(s) - English
Resource type - Journals
ISSN - 2277-3061
DOI - 10.24297/ijct.v3i1b.6778
Subject(s) - terminal and nonterminal symbols , combinatorics , mathematics , arithmetic , symbol (formal) , zero (linguistics) , variable (mathematics) , terminal (telecommunication) , computer science , philosophy , parsing , telecommunications , linguistics , artificial intelligence , programming language , mathematical analysis
In automata theory Greibach Normal Form shows that A->aV
n*, where ‘a’ is terminal symbol and Vn is nonterminal symbol where * shows zero or more rates of Vn [1]. Most popular questions, conversion of following cyclic CNF into GNF are:
Question 1 S->AA | a, A->SS | b
Question 2 S->AB, A->BS | b, B->SA | a
Question 3 S->AB, A->BS | b, B->AS | a [1]
To solve these questions, we need two technical lemmas and required one or more another variable like Z1. In these questions, we have cyclic nature of production called cyclic CNF. We have modified the same rule by which we get the more reliable answer with less number of productions in right hand side without using lemmas and any another variable. This above method can be applied on all problems by which we produce the GNF.