1
$\begingroup$

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}

$\endgroup$
4
  • $\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$ Commented Mar 26, 2021 at 23:38
  • $\begingroup$ cs.stackexchange.com/q/1331/755 $\endgroup$
    – D.W.
    Commented Mar 26, 2021 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
    Commented Mar 26, 2021 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$ Commented Mar 27, 2021 at 0:46

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ the word "aabb" is not included for example $\endgroup$ Commented Mar 27, 2021 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
    Commented Mar 27, 2021 at 0:55
  • $\begingroup$ yes i agree with you. $\endgroup$ Commented Mar 27, 2021 at 1:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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