Is ε terminal in context-free?

3.6k views Asked by At
R: S ---> aSb
   S ---> SS
   S ---> ε

How should I write the grammar for these expressions?

Is it true to writing like this?

G = ({S}, {a, b}, {S ---> aSb, S ---> SS, S ---> ε}, {S})

or like this (adding epsilon to terminals):

G = ({S}, {a, b, ε}, {S ---> aSb, S ---> SS, S ---> ε}, {S})

which is the correct one?

1

There are 1 answers

2
rici On BEST ANSWER

ε is a way to make a zero- length sequence visible. It is not a grammar symbol.

The actual production is: S →   — that is, S can produce nothing — but the invisibility of nothing makes it hard to read. So we usually write ε, which is more legible. You should read it as nothing, though.