618 views
0 votes
0 votes
Are NULL productions in the form of S->ɛ allowed in CFG and regular grammar?

1 Answer

0 votes
0 votes

 Yes this type of production is allowed in both CFG and Regular Grammar. ' ε' is a valid string of length 0.

Let production be in format u->v

CFG: It should satisfy conditions of type1 and type 0 grammars. Only restriction is u ∈ V (V here is a single variable). So it can also generate S->ε.

Regular Grammar: u ∈ V (single variable) and v ∈ T* + T*V or v ∈ T*+VT* so from this you can generate S->ε. 

Hence both generates the above production.

Hope this helps.

 

No related questions found