I want to generate a grammar that can't generate the words $qw$ and $wq$ but can generate the word $qwwq$. In other words, $L(G)=\{m ∈ \{q,w\}^* \mid m \neq wq,qw \}$.

My grammar:

\begin{align} &S \to qSw \mid wSq \mid qXq \mid wXw\\ &S \to qYw \mid wYq \mid q \mid w\\ &X \to qX \mid wX \mid qXw \mid wXq \mid ε \\ &Y \to qw \mid wq \\ \end{align}

  • $\begingroup$ @D.W. I don't a finite number of words, what I want is the whole words in {q,w}* except the "qw" and the "wq" $\endgroup$ Mar 26 at 23:38
  • $\begingroup$ cs.stackexchange.com/q/1331/755 $\endgroup$
    – D.W.
    Mar 26 at 23:51
  • 2
    $\begingroup$ Your language is regular as it's the complement of the finite (and hence regular) language $\{wq, qw\}$. $\endgroup$
    – Steven
    Mar 26 at 23:53
  • $\begingroup$ @Steven yupp, do you have any idea how we can write it i just wrote CFG because i want to convert it to CNF after $\endgroup$ Mar 27 at 0:46

How about \begin{align*} S&\to q\mid w\mid qqB \mid wwB \mid qwA\mid wqA\mid \varepsilon \\ A&\to qB\mid wB \\ B&\to qB\mid wB\mid \varepsilon \end{align*}

We can just explicitly include strings of length 0, 1 or 2 that are allowed, but add another non-terminal after the length two strings which are not allowed to force us to add at least one more terminal, then make sure after that we can add any letters we want in any order.

  • $\begingroup$ the word "aabb" is not included for example $\endgroup$ Mar 27 at 0:47
  • $\begingroup$ @MandiJoseph You're right I forgot to include the $B$ after the $qq$ and $ww$. I've edited it. By the way you will want to add a rule $S\to \varepsilon$ to the grammar you've written. $\endgroup$
    – awillia91
    Mar 27 at 0:55
  • $\begingroup$ yes i agree with you. $\endgroup$ Mar 27 at 1:07

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.