By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,492 Members | 1,652 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,492 IT Pros & Developers. It's quick & easy.

inherent ambiguity

P: 21
how do one prove that the language is inherently ambigous? like for example in languages that use unions such as
L = L1 U L2, where
L1 = {a^m b^m c^n | m,n>0}
L2 = {a^m b^n c^n | m,n>0}
Nov 14 '08 #1
Share this Question
Share on Google+
1 Reply


Expert 10K+
P: 11,448
how do one prove that the language is inherently ambigous? like for example in languages that use unions such as
L = L1 U L2, where
L1 = {a^m b^m c^n | m,n>0}
L2 = {a^m b^n c^n | m,n>0}
If the intersection of L1 and L2 isn't empty while L1 != L2 the union of both
languages L1 U L2 is ambiguous. Note that the problem L1 == L2? is an
undecidable problem. See the Post Correspondence Problem for a fundamental
proof.

kind regards,

Jos
Nov 14 '08 #2

Post your reply

Sign in to post your reply or Sign up for a free account.