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

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\}^*\}$$

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.

• Welcome to Computer Science! Your question is a quite basic (if "tricky") one. Let me direct you towards our reference material which cover some fundamentals you may be missing in detail. Please work through the related questions listed there, try to solve your problem again and edit to include your attempts along with the specific problems you encountered. Good luck!
– Raphael
Oct 16 '17 at 20:37
• Hint: "the language specifies that the number of leading and trailing 1s must be the same" -- it does not. Look more closely; the task here is to be careful reading things. The proof itself is almost trivial.
– Raphael
Oct 16 '17 at 20:39

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.

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.

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.