grammar - One Language and Proof How it's ambiguous? -

i took midterm couldn't answer question.

how can show following language ambiguous ?

l={a ⁿ b^m c ^p : n≠m} u {a ⁿ b^m c ^p : m≠p}

i think hard, can me automated tools or ... how can prove ?

consider 1 possible grammar language {anbmcp : n≠m}:

s → x c | x b c x → ε | x b → | a b → b | b b c → ε | c c 

in grammar, left-most derivation of word not expand , c until other non-terminals have been expanded. similar grammar other half of union (anbmcp : m≠p} expand as before other non-terminal expanded. word in intersection of 2 subsets therefore have (at least) 2 distinct derivations.

proving language inherently ambiguous requires proving above true grammar language. such proof based on ogden's lemma, generalization of pumping lemma context free languages; proof consists of demonstrating word can "pumped" in 2 different ways.

it relatively easy find proof similar language {anbmcp : n=m} ∪ {anbmcp : m=p} inherently ambiguous: it's used example in textbooks on formal language theory. think proof language "more difficult" in requires consideration of more cases, should similar.

an alternative approach analytic method of flajolet.