Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
added 61 characters in body
Source Link

If A and B are regular, then prove that A@B={xy| x is in A, y is in B and |x|=|y|}$A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free.

So ImI'm trying to come up with the proof that looks something like this. Knowing that A$A$ and B$B$ are regular, we can conclude that there exists NFA for A$A$ and B$B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept x$x$ from A$A$ and another PDA that would accept y$y$ from B$B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of x$x$ and y$y$ too and accepts only in the case when x=y$x=y$.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given A$A$ and B$B$ are regular final the PDA will always accept A@B$A@B$.

If A and B are regular, then prove that A@B={xy| x is in A, y is in B and |x|=|y|} is always context free.

So Im trying to come up with the proof that looks something like this. Knowing that A and B are regular, we can conclude that there exists NFA for A and B respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept x from A and another PDA that would accept y from B. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of x and y too and accepts only in the case when x=y.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given A and B are regular final PDA will always accept A@B

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free.

So I'm trying to come up with the proof that looks something like this. Knowing that $A$ and $B$ are regular, we can conclude that there exists NFA for $A$ and $B$ respectively. Then, we can work out these NFA into two separate PDA: one PDA that would accept $x$ from $A$ and another PDA that would accept $y$ from $B$. Then we need to somehow merge two PDAs into one modifying it so that it controls the length of $x$ and $y$ too and accepts only in the case when $x=y$.

I am just trying to come up with the set of legitimate steps that would follow through this, and that these steps would always work so that given $A$ and $B$ are regular final the PDA will always accept $A@B$.

Tweeted twitter.com/#!/StackCompSci/status/520792326432915456
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393

Prove given languagethat the equal-length concatenation of regular languages is context free

added 656 characters in body
Source Link
romada
  • 89
  • 1
  • 6
Loading
Source Link
romada
  • 89
  • 1
  • 6
Loading