0 votes 0 votes Can GNF contains ε example - S-----> aε is it in GNF i.e can a terminal have an ε afterwards and will that be in GNF? Theory of Computation theory-of-computation context-free-language + – iarnav asked Sep 14, 2017 iarnav 1.4k views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Warlock lord commented Sep 14, 2017 reply Follow Share I'm not sure what you mean by ε here. If that is equivalent to 'lambda' (null, sort of) then, no. Before converting any grammar into GNF we must follow some steps like eliminating null productions, unit productions and left recursion. 1 votes 1 votes G Shaheena commented Sep 16, 2017 reply Follow Share gnf means it is in the form of S->a$\alpha$where $\alpha$ is set of non-terminals your question is $\epsilon$ is allowed after a i.e after terminal $\epsilon$ is allowed after terminal because with epsilon or without epsilon production is same so there is no change in production by including epsilon 1 votes 1 votes Warlock lord commented Sep 16, 2017 reply Follow Share yes you're right. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes GNF allow production of form A --> BX where A ∈ V , B∈ T , X ∈ V* where V=variables T=terminals example - S-----> aε is it in GNF i.e can a terminal have an ε afterwards and will that be in GNF? I guess by ε you mean null element. GNF does not allow ε . but S-----> aε is allowed as it is same as S--->a. GNF states that each production should start with a terminal followed by 0 or more no of terminals. Satyajeet Singh answered Sep 14, 2017 • edited Sep 14, 2017 by Satyajeet Singh Satyajeet Singh comment Share Follow See 1 comment See all 1 1 comment reply hs_yadav commented Sep 14, 2017 reply Follow Share @Satyajeet Singhs. production rule for GNF is like this... V->TV* V->T where T stands for terminal and V for variable(non-terminals) 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes GNF , A -> aV, where V = Kleene closure of variables. in kleene closure, epsilon is possible hence , A ->a∈ Is possible . AnilGoudar answered Sep 16, 2017 AnilGoudar comment Share Follow See all 0 reply Please log in or register to add a comment.