-2
$\begingroup$

I have just started learning formal languages and here is a question I am facing a little hurdle:

Construct a context-free grammar for $\{ a^{2n}b^{2n} \mid n \ge 0 \}$.

This was what I got at first. $$S \to ab\mid aS\mid Sb\mid ab$$ Now I am getting this, $$S\to \epsilon$$

$$S\to aaSbb$$

$$G=(V,\Sigma,R,S)=(\{S,a,b\},\{a,b\},R,S)$$

$$R= \{S \to aaSbb\mid \epsilon\}$$ Is the approach to this question, right or is it done in a different way?

Improve this question
$\endgroup$
3
  • $\begingroup$ Evidently not, because the desired language has an even number of as and an even number of bs, while your proposed grammar immediately derives a string (ab) which does not have an even number of anything (through two different productions, which is redundant). $\endgroup$
    – rici
    Jun 17 at 6:38
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W. ♦
    Jun 17 at 6:52
  • $\begingroup$ cs.stackexchange.com/q/11315/755 $\endgroup$
    – D.W. ♦
    Jun 17 at 6:52
1
$\begingroup$

Here is a derivation in your grammar:

$$ S \to aS \to aab. $$

The word $aab$ does not belong to your language, hence your grammar is incorrect.

Improve this answer
$\endgroup$
-1
$\begingroup$

I think this is the solution: $$S\to \epsilon \mid aaSbb $$

Improve this answer
$\endgroup$
-1
$\begingroup$

the second grammer you wrote, is right. it can involve all strings belongs to the language with no extra string.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ We'd prefer answers that come with explanation, justification, and/or proof of correctness. We want to share not just the correct answer but information that will help others figure out how to obtain that answer or how to know that it is correct. $\endgroup$
    – D.W. ♦
    Aug 16 at 3:59

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.