# What is the generated grammar for this language?

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 | ε})

• What ls $\lambda$ supposed to be? Mar 12 at 22:09
• epsilon (empty word) .. I'll change it to ε 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$$

• can we do it like this? {S->abS|bcS|Sab|Sbc|aSb|bSc|aS|bS|cS|Sa|Sb|Sc|ϵ} Mar 12 at 22:40
• @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. Mar 12 at 22:50
• that's right ... thank you 4 the information. Mar 12 at 22:56