2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – Raphael Oct 16 '17 at 20:37
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Oct 16 '17 at 20:39
2
$\begingroup$

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(101) 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)^*$.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.