0

I want to write a grammar for a language not ending on "01". I found the regular expression here:

regular expression

I tried the following:

S-->1S11| 0S10|01S00|00|10|11|lambda

Somebody please guide me.

Zulfi.

zak100
  • 177
  • Assuming you meant epsilon (i.e. the empty string) instead of lambda, you are getting there. Two hints: (1) what about strings of length 1? (2) for strings of length 2+, consider creating a new non-terminal symbol. (Note that the regular expression given in the question is wrong - the regular expression given in the answer below is correct). – roundsquare Dec 03 '19 at 02:17
  • This is the regular expression provided in the answer of the above link. Please guide me what's wrong with this: epsilon + 0 + 1 + (0 + 1)^*(00 + 10 + 11): – zak100 Dec 03 '19 at 03:29
  • 1
    @roundsquare some texts do use $\lambda$ instead of $\epsilon$ for the empty string. – MJD Dec 03 '19 at 12:36

1 Answers1

1

With the regular expression:

$\epsilon+0+1+(0+1)^*(00+10+11)$

There are four possibilities: (1) empty string; (2) $0$; (3) $1$; and (4) longer strings.

We can directly replicate this in the grammar

$S \rightarrow \epsilon|0|1|T$

$T \rightarrow 0T|1T|00|10|11$

As you can see, $S$ can directly do the first three possibilities or do the fourth possibility using $T$. $T$ builds up bigger strings by allowing any number of $0$'s and $1$'s and then ending with either $00$, $10$, or $11$ (to prevent it from ending with $01$).

roundsquare
  • 1,447