show that a language is context-free by giving a pushdown automaton that accepts the language

Question

Given the language $K$ : the words x$y where x and y have odd lengths on {a, b} and the median letter of x is equal to the median letter of y.

Example:

abb$b and

aaaaa$bab are in K

aba$abaab isn't in K

So i am kinda lost here, i am trying to figure out how to do this problem. I struggle to understand how will it recognize that the numbers are odd and how can it know that the median of both words are the same letter.

Could anyone help please, thanks a lot.

I started this drawing but i am so unsure on what to put on state 2 and 3 to make it work. ( I used : http://madebyevan.com/fsm/ if u wanna draw).

EDIT I wrote a new solution this seem ok, if someone could confirm it would be nice.

Answer 1

A CFG would be much easier , then it can be converted to a PDA :

The $ was replaced by #

S --> A # A | B # B

A --> ΣAΣ | a

B --> ΣBΣ | b

Σ --> a | b

Hopefully you can see that A generates all strings of odd length with a in middle and B generates all strings of odd length with b in middle ,

And so S generates the strings correctly

Answer 2

Its been a little while since I've done this stuff, so sorry if my description isn't great. But here is an approach you can flesh out.

• Start in $x_L$. This state scans the input and pushes onto the stack until it randomly decides to switch to $x_?$ state.
• In $x_?$ state it looks to see if the current character is $a$ or $b$ and moves to $x_a$ or $x_b$ depending on which one it sees.
• In either $x_a$ or $x_b$ it starts popping off the stack. If it gets to $\#$ before the stack is empty or it empties the stack before it gets to $\#$ it fails. Otherwise, if it gets to $\#$ exactly when the stack is empty, it moves to $y^a_L$ or $y^b_L$ depending on if it is in $x_a$ or $x_b$.

At this point, if it hasn't failed, it knows that $x$ is of odd length and if the middle character is $a$ or $b$. Then, you can do something similar for $y$ and only succeed if both middle characters are the same.

Hope this helps.