Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular

Question

Show that the following language $L$ is regular by describing it using a regular expression. $$L = \{1^n w 1^n \mid n > 0 \text{ and }w ∈ \{0,1\}^*\} $$

My (apparently incorrect) answer:

Given $w ∈ \{0,1\}^*$ , we can rewrite $L$ as: $1^n(0\cup1)^*1^n\ for\ n ≥ 0$

However, since the language specifies that the number of leading and trailing $1$s must be the same - this language is not​ ​regular​.

My justification:

1. For every regular language, there is (by definition) a finite automaton that accepts that language
2. The given language $L$ requires an equivalent count of leading and trailing $1$​s
3. Finite automata are not capable of maintaining a count.

Since​ ​no​ ​finite​ ​automata​ ​can​ ​accept​ ​the​ ​language​ $L$​,​ $​L$​ ​is​ ​not​ ​regular.

Can anyone explain to me why this language is regular? I'm completely stumped. I can see that it could be pumped using the Pumping Lemma (thereby proving regularity), but my brain just refuses to recognize that an FSM could accept this language.

Answer 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 = L'$

To prove $L'$ is regular jus note that it is the concatenation of three trivial regular languages:

$L_1 = \{ 1 \}$, $L_2= \{ (0 \cup 1)^* \}$, $L_3 = \{1\}$

$L' = L_1 \cdot L_2 \cdot L_3$

And regular languages are closed under concatenation.

Answer 2

My answer is just a hint. The following pattern should lead you to the right answer:

These strings belong to the language:
$w = 11 \Rightarrow 1^1\epsilon 1^1, n=1$
$w = 1011 \Rightarrow 1^1(01) 1^1, n=1$
$w = 11011 \Rightarrow 1^1(101) 1^1, n=1$ or $1^2(0) 1^2, n=2$
$w = 1001011 \Rightarrow 1^1(00101) 1^1, n=1$
$w = 11111 \Rightarrow 1^1(111) 1^1, n=1$ or $1^2(1) 1^2, n=2$
$w = 101010011 \Rightarrow 1^1 (0101001) 1^1, n=1$
$\cdots$
Finally, if $w=1^nw 1^n$ then it can be written as $1v1$, where $w,v \in (0+1)^*$, i.e. 1Σ*1.

These strings DO NOT belong to the language:
$w=0$
$w=01$
$w=100$
$w=0000$
$w=0001$
$w=1000010$
$\cdots$

Yo may want to look at the first and the last symbols of each string.

Answer 3

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.