0
$\begingroup$

I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Hint: This problem is really, really easy. $\endgroup$ – gnasher729 Jun 4 '20 at 6:06
  • $\begingroup$ Stronger hint: You put equal numbers of characters to each side, and you make sure there’s a b in the middle by putting a b in the middle. $\endgroup$ – gnasher729 Jun 4 '20 at 6:08
-1
$\begingroup$

PDA:

Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"

CFG:

$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$

Yea, thats everything in the CFG!

Improve this answer
$\endgroup$
5
  • $\begingroup$ How are you supposed to do all that in a CFG? $\endgroup$ – C.Cam Jun 4 '20 at 4:10
  • $\begingroup$ Counting is simple. Use the stack. Guessing is literally usimg the non-determinism and each letter we read we both guess that its the middle and its not the middle, and the rest is just comparing the rest to the stack $\endgroup$ – nir shahar Jun 4 '20 at 4:15
  • $\begingroup$ Makes no sense to me at all. $\endgroup$ – gnasher729 Jun 4 '20 at 6:06
  • $\begingroup$ oh sorry, i mistook it for a PDA. $\endgroup$ – nir shahar Jun 4 '20 at 9:19
  • $\begingroup$ Just fixed it, hope it helps now! $\endgroup$ – nir shahar Jun 4 '20 at 9:23

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.