4
Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang constructed, in their paper Regular Expressions: New Results and Open Problem, a regular expression of size $O(n)$ for which the minimal rejected word has size $\Omega(n2^n)$; here $n$ is an arbitrary parameter. The regular expression can be converted to an NFA with $O(n)$ states and transitions ...
2
Consider the language $L = \{uv\mid u, v\in\Sigma^*, |u|=|v|\wedge u\neq v\}$. I claim that $L$ is context-free, it is not regular (a simple pumping lemma proof can do the trick), but $L^*$ is regular, without being equal to $\Sigma^*$, so that means that $L^*\overline{L^*}$ is regular and satisfies your conditions.
Now let's show that if we denote $L'= (\...
1
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length.
Consider $w = b^pab^p \in L$.
By the pumping lemma there is some integer $1\le i \le p$ such that $b^{p+ki} a b^p \in L$ for all choices of an integer $k \ge -1$.
However, choosing $k=-1$ yields $b^{p-i} a b^p \not\in L$, which provides the sought contradiction.
1
You should consider (one of) the word $w$ of minimal length in $S$, and show that for this word in particular, you can reach the conclusion that $|l| = 0$.
1
Believe it or not the language $L$ is equivalent to:
$L' = 1(0 \cup 1)^*1$ which is regular
Proof:
Given $x \in L'$, then $x=1^1w1^1$ with $w \in (0 \cup 1)^*$, so $x \in L$ (just take $n=1$)
Given $x \in L$, then $x = 1^n w 1^n = 1 (1^{n-1}w1^{n-1}) 1$ which is always possible because $n > 0$; but $(1^{n-1}w1^{n-1}) \in (0 \cup 1)^*$ so $x \in L'$
so $L ...
1
Let $x=1^kw1^k\in L$ (with $n=k$).
Then, define $w':=1^{k-1}w1^{k-1}$, and we will have $x=1w'1\in L$ (with $n=1$).
Try to use this trick to "remove" the $n$ in the question. After "removing" it, constructing a finite state machine is easy.
Only top voted, non community-wiki answers of a minimum length are eligible
