I want to construct a regular grammar that generates words that contain both "ab" and "bc" as subwords with the alphabet of the terminal symbols {a,b,c}

My solution so far is

G=(Vn={S,X,Y},Vt={a,b,c},S,F={ S-> aS | bS | cS | abX | cbX, X-> aX | bX | cX | ε})

  • $\begingroup$ What ls $\lambda$ supposed to be? $\endgroup$ Mar 12 at 22:09
  • $\begingroup$ epsilon (empty word) .. I'll change it to ε $\endgroup$
    – James Tan
    Mar 12 at 22:17

Your solution so far is incorrect. According to your solution, we have the derivation

S -> abX -> ab

which does not contain bc as a substring.

Your solution also has a non-terminal Y, but does not appear in any production rules.

A correct grammar follows, with start symbol $S$:

$S \to aS$
$S \to bS$
$S \to cS$
$S \to abcA$
$S \to abX$
$S \to bcY$

$A \to aA$
$A \to bA$
$A \to cA$
$A \to \epsilon$

$X \to aX$
$X \to bX$
$X \to cX$
$X \to bcA$

$Y \to aY$
$Y \to bY$
$Y \to cY$
$Y \to abA$

  • $\begingroup$ can we do it like this? {S->abS|bcS|Sab|Sbc|aSb|bSc|aS|bS|cS|Sa|Sb|Sc|ϵ} $\endgroup$
    – James Tan
    Mar 12 at 22:40
  • $\begingroup$ @Johny that's not a regular grammar. And even if it were, it's still wrong. We would have $S \to \epsilon$, but $\epsilon$ does not have $ab$ as a substring. $\endgroup$ Mar 12 at 22:50
  • $\begingroup$ that's right ... thank you 4 the information. $\endgroup$
    – James Tan
    Mar 12 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.