Timeline for Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Mar 18 at 20:30 | history | suggested | NerdOnTour | CC BY-SA 4.0 |
I found the proof conclusion hard to follow and therefore I have edited it. In particular, you wrote that "$w_2$ and $v_1$ commute". For me, this would mean that $w_2 v_1$ = $v_1 w_2$, which is clearly not the case here (and would also be irrelevant). I hope my edit makes the OP's idea more precise.
|
| Mar 18 at 10:28 | review | Suggested edits | |||
| S Mar 18 at 20:30 | |||||
| Jun 9, 2022 at 18:41 | comment | added | gnasher729 | S->BA, B->aSb->abb, A->a, S->abba. | |
| Mar 15, 2019 at 9:14 | comment | added | Raphael | @George.Zhao I don't follow. Cleary, $abba \in L$ with $x = ab$ and $y=ba$? | |
| Mar 15, 2019 at 7:28 | comment | added | George.Zhao | If we use this grammar, we can generate a string like: $ S \rightarrow AB $ $ A \rightarrow a $ $ B \rightarrow bBa, then B \rightarrow b $ After that, we got a S as abba! This is not equal to the raw language L, is there a mistake here? | |
| Apr 30, 2012 at 14:13 | history | tweeted | twitter.com/#!/StackCompSci/status/196965530769428481 | ||
| Mar 15, 2012 at 23:14 | history | edited | Raphael | CC BY-SA 3.0 |
typos
|
| Mar 13, 2012 at 16:12 | history | edited | Raphael | CC BY-SA 3.0 |
adding note on how to prove the central statement
|
| S Mar 13, 2012 at 16:03 | history | suggested | Dave Clarke | CC BY-SA 3.0 |
More fixes of the latex.
|
| Mar 13, 2012 at 16:01 | vote | accept | Dave Clarke | ||
| Mar 13, 2012 at 15:58 | review | Suggested edits | |||
| S Mar 13, 2012 at 16:03 | |||||
| Mar 13, 2012 at 15:54 | history | edited | Raphael | CC BY-SA 3.0 |
deleted 4 characters in body
|
| Mar 13, 2012 at 15:54 | review | Suggested edits | |||
| Mar 13, 2012 at 15:54 | |||||
| Mar 13, 2012 at 14:36 | history | answered | Raphael | CC BY-SA 3.0 |