0
$\begingroup$

I faced a problem. What is the proof to say that if yx is in a Context-Free Language we can say that xy is also in a context-free language.

C is a Context-Free Language.

xy where yx belongs to C(Context-free language)

I think we can use the PDA defining C and edit final states.

Any ideas? thank you.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I'm not sure what you're asking. Please define all notation carefully. What's C? What is the precise statement of the fact you want to prove? Figuring out what you're trying to prove is the first step towards proving something. $\endgroup$
    – D.W. ♦
    Commented Jun 5, 2020 at 3:34
  • 1
    $\begingroup$ What are the $x$ and the $y$? Is any of them just a character or are they both strings? $\endgroup$
    – frabala
    Commented Jun 5, 2020 at 6:56
  • 1
    $\begingroup$ Also, can any of the $x$ or $y$ be the empty string? $\endgroup$
    – frabala
    Commented Jun 5, 2020 at 7:04
  • 2
    $\begingroup$ Ik think you mean the operation rotation, conjugation, or cyclic shift. I do not know of a really easy proof. Easy proof for context-free languages being closed under cyclic shift. Accepted answer has a PDA proof, also recalled in another reaction is an answer with CFG by Hopcroft & Ullmann. $\endgroup$
    – Hendrik Jan
    Commented Jun 5, 2020 at 10:30

0

Reset to default