# How to prove that these formulas are uniquely readable.

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.

• 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. Jun 4 at 22:37
• 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. Jun 5 at 0:04
• @AndreasBlass Thank you very much! Jun 5 at 14:24