1
$\begingroup$

I have the following problem, create a Grammar on the Language {1,0} that accepts

"strings with a length divisible by 3, or strings with a number of 0s divisible by 3, or BOTH".

I created grammars for each part, but I'm not sure how to account for the "BOTH" clause.

I started by making a regular expression:

1*(01*01*01*)+|((0|1)(0|1)(0|1))+

Then I made the following Grammars for each of the two main parts:

1*(01*01*01*)+

becomes

S_1 -> 1F | F
F   -> 1F | 0G
G   -> 1G | 0H
H   -> 1H | 0M
M   -> F | (empty)

and

((0|1)(0|1)(0|1))+

becomes

S_2 -> 0C | 1C
C   -> 0D | 1D
D   -> 0E | 1E
E   -> S | (empty)

My question is, if I just use the central or in the regular expression and start the complete Grammar by branching to one of the two Grammars I made with no cross over*, will it somehow potentially compromise the "or BOTH" requirement in some cases? Or is that extra requirement just a red herring and will be necessarily satisfied by covering both of the base requirements? As far as I can tell, both are more or less completely independent of one another.

*ie just tack the two together with this at the start:

S -> S_1 | S_2
...
$\endgroup$
2
$\begingroup$

$S \to S_1 | S_2$

That is correct. A grammar doesn't care which derivation it used, or how many could have been used, as long as at least one derivation is valid.

Now if the question said but not both, then it would get complicated!

$\endgroup$

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.