GATE CSE
First time here? Checkout the FAQ!
x
0 votes
40 views

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 Loyal (3.4k points)   | 40 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 Junior (775 points)  
edited by

@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 vote
GNF ,

 A -> aV,

 where V = Kleene closure of variables.

in kleene closure, epsilon is possible

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


Top Users Sep 2017
  1. Habibkhan

    7194 Points

  2. Warrior

    2686 Points

  3. Arjun

    2594 Points

  4. rishu_darkshadow

    2568 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,164 questions
33,742 answers
79,996 comments
31,125 users