Prove a language isn't regular using Myhill-Nerode thm.

173 Views Asked by At

Let $L$, a language above $\Sigma = \{x,y, (,),+,* \}$. $L$ can be defined recursively as follows:

Basis Clause: $x$ and $y$ are in $L$.
Inductive Clause: If $\alpha$ and $\beta$ are in $L$, then $(\alpha + \beta)$ and $(\alpha * \beta)$ are in $L$.
Extremal Clause: Nothing is in $L$ unless it is obtained from the above two clauses.

The guidance is to prove $L$ isn't regular using Myhill–Nerode theorem.

I'm trying to think about two expressions, $\alpha \ne \beta \in L$ (and later on, a subset of $L$) such that for every $w\in \Sigma^*$: $\alpha w \in L \iff \beta w \in L$, but something isn't working.

I'd be glad for help!

1

There are 1 best solutions below

2
On BEST ANSWER

HINT: Consider the strings $\underbrace{((\ldots((}_nx$ for $n\in\Bbb N$.