1
$\begingroup$

Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$

whereas $|w|_a$ is the number $a$'s in the word $w$ and $|w|_b$ is the number of $b$'s in $w$.

We should give a grammar (of any type) for $A4$.

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

I can't seem to be able to give a comprehensive grammar for this without breaking that rule. Any tip would be greatly appreciated.

$\endgroup$
3
$\begingroup$

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

This characterization of words not in $A4$ is nice. However, what we want is to produce words in $A$. Let us classify the words in $A4$ as the disjoint union of the following 3 pieces.

  1. the words where the number of $a$'s is even and the number of $b$'s is even.
  2. the words where the number of $a$'s is odd and the number of $b$'s is even.
  3. the words where the number of $a$'s is odd and the number of $b$'s is odd.

Now use a distinct nonterminal to represent each piece.

The above hint should be enough to set you moving.

Once you have got your own solution, or you run into another bottleneck, you could mouseover the following to reveal the spoiler.

To facilitate writing the grammar, we will add a non-terminal to represent the 4-th piece.

$\quad$4. the words where the number of $a$'s is even and the number of $b$'s is odd.

Here is the grammar, where non-terminal $S_{i,j}$ represents the words whose number of $a$'s is $i$ modulo 2 and whose number of $b$'s is $j$ modulo 2.

$S\to S_{0,0}\mid S_{1,0}\mid S_{1,1}$
$S_{0,0}\to cS_{0,0}\mid aS_{1,0}\mid bS_{0,1}\mid\epsilon $
$S_{0,1}\to cS_{0,1}\mid aS_{1,1}\mid bS_{0,0}$
$S_{1,0}\to cS_{1,0}\mid aS_{0,0}\mid bS_{1,1}$
$S_{1,1}\to cS_{1,1}\mid aS_{0,1}\mid bS_{1,0}$

$\endgroup$
  • $\begingroup$ Here's my attempt: S → S1 | S2 | S3 S1 → ε | aaS1 | bbS1 | cS1 S2 → a | aaS2 | bbS2 | cS2 S3 → abS3 | aS3b | cS3 And the swapping productions: ab → ba ba → ab ac → ca ca → ac ca → ac cb → bc bc → cb Is there a more elegant way to do this? $\endgroup$ – user1221 Jan 19 at 20:29
  • $\begingroup$ Not sure what your production rules are. You could check my spoiler. $\endgroup$ – Apass.Jack Jan 20 at 16:45
0
$\begingroup$

Your language is regular. It contains all words over $\{a,b,c\}$ with either an even number of $b$’s or an odd number of $a$’s (or both).

$\endgroup$
0
$\begingroup$

Let S be the start symbol. S represents anything that doesn't have an even number of a's and odd number of b's. Further three symbols: A is not (odd a's and odd b's), B is not (even a's and even b's), C is not (odd a's and even b's).

An empty string is in the language derived from S, A or C, but not B. Therefore we have rules

S->eps
A->eps
C->eps

c doesn't change anything, so we have rules

S->cS
A->cA
B->cB
C->cC

a and b change what should come next. Check the following careful, easy to get wrong.

S->aA, S->bB
A->aS, A->bC
B->aC, B->bS
C->aB, C->bA
$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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