formal languages write context-free grammar

47 Views Asked by At

I have been confusing a question for 2 days. I think I solved the question, but I don't know if it's true. Can you help me tell me I did it right or wrong?

The question is ;

Write a context-free grammar for the language $$L = \{ w \mid \text{the first, middle and last symbols of $w$ are the same}\}$$ defined on the alphabet $\{0,1\}$.

I found the answer like this.

$S \to 0A0 \mid 1A1$

$A \to 0S0 \mid 1S1$

Thank you from now...

1

There are 1 best solutions below

4
On BEST ANSWER

If I am not wrong, a possible grammar could be

$S \to UTU +U$

$T \to 0T0 + 0T1 + 1T0 + 1T1 + U$

$U \to 0 + 1$