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.
Best Answer
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