The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
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?


asked in Theory of Computation by Boss (5.2k points) | 57 views
yes, it is allowed

@ G Shaheena  Can you post some source?

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.

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
yes you're right.

2 Answers

+1 vote

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.


answered by Active (1.1k points)
edited by

@Satyajeet Singhs.

production rule for GNF is like this...


V->T    where T stands for terminal and  V for variable(non-terminals)

+1 vote

 A -> aV,

 where V = Kleene closure of variables.

in kleene closure, epsilon is possible

hence , A ->a∈ Is possible .
answered by Loyal (3.5k points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

28,834 questions
36,686 answers
34,640 users