Timeline for When is the concatenation of two regular languages unambiguous?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29, 2015 at 20:36 | comment | added | Yuval Filmus | Yes, it doesn't sound too efficient, though there is always the option of doing it in a smart way. I'm not aware of any specific algorithm for this problem, but one might exist. | |
| Jul 29, 2015 at 20:34 | comment | added | rstern | Thanks for the hint! So if I understand, I can construct an NFA for ambiguous words in $AB$ and then test that automaton for emptiness. The tricky part seems to be "ensuring that the switch from $A$ to $B$ happens at two different points". I'm not sure how to do that other than taking the cross product (?) of two $AB$ DFAs and deleting all of the ($A$-terminal, $A$-terminal) product states—I'm handwaving, I'm worried that the transition from $AB$ NFA to $AB$ DFA would screw with the idea of $A$-terminal. Sounds, um, inefficient though; is there a known algorithm suitable for software? | |
| Jul 29, 2015 at 19:46 | history | answered | Yuval Filmus | CC BY-SA 3.0 |