0
$\begingroup$

We have the inductively defined set, M, as follows(this is a language over the alpabet $(e,a,\bar{a},b,\bar{b})$:

We let $M$ be the smallest set so that

$e\in M$

If $x,y\in M$ then $xy\in M$

If $x \in M$ then $ax\bar{a}\in M$

If $x \in M$ then $bx\bar{b}\in M$

How to I prove that this set is uniquely readable? That is, if $f\in M$. Then F is either $xy$ for uniquely x and y. Or f is $ax\bar{a}$ for uniquely x. Or f is $bx\bar{b}$ for uniquely x. Or f is e.

I tried using the proof that the formulaes in proposition logic are uniquely readable. There we are supposed to show that no formula is an initial segment of another formula. But I couldn't get that to work.

$\endgroup$
3
  • $\begingroup$ What is the context here? You have used the logic and recursion tags, but the question seems more to do with parsing or grammar theory. $\endgroup$
    – Rob Arthan
    Jun 4 at 22:37
  • 2
    $\begingroup$ Unless I'm misunderstanding something, what you're trying to prove is false. $eee$ is $xy$ with $x=ee$ and $y=e$, and it's also $xy$ with $x=e$ and $y=ee$. So the uniqueness requirement fails. $\endgroup$
    – Andreas Blass
    Jun 5 at 0:04
  • $\begingroup$ @AndreasBlass Thank you very much! $\endgroup$
    – user394334
    Jun 5 at 14:24

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .