$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$

Any idea? I have problem with this kind of task.

  • $\begingroup$ Have you studied the reference question and answers How to prove that a language is not regular?? $\endgroup$ – Apass.Jack Feb 11 at 22:08
  • $\begingroup$ Please don't change your question in a way that invalidates existing answers. If you asked the wrong question, please ask a new question -- and take more care with future questions to avoid wasting people's time on something that wasn't what you really wanted to know about. $\endgroup$ – D.W. Feb 11 at 23:28
  • 1
    $\begingroup$ Unfortunately or fortunately, the updated question is much easier. We can always choose $y$ to be the empty word. So, $L$ is the language of all words. May I rollback the question to its previous version? $\endgroup$ – Apass.Jack Feb 11 at 23:38
  • $\begingroup$ @Apass.Jack yes $\endgroup$ – PoliteMan Feb 11 at 23:42

I am afraid that you cannot construct a DFA for $L$ since it is not regular.

Intuitively, a finite automaton cannot even make sure the number of $a$'s and the number of $b$'s are the same since its finite memory cannot keep track of the number of the $a$'s in the initial part of $a^nb^n$ when $n$ become sufficient large.

How to prove that language is not regular?

  • Use the pumping lemma. For example, what about a word that barely satisfies the condition such as $a^pb^{p+10}$?
  • Use Myhill–Nerode theorem. How about elements $a^n$ for all $n$? Does any of two of them belong to the same Myhill–Nerode class?

Exercise 1. Let $\lfloor x\rfloor_a$ be the minimum number of consecutive $a$'s in $x$ and $\lceil x\rceil_a$ be the maximum number of consecutive $a$'s in $x$, where $x\in\{a,b\}^*$ contains $a$. $\lfloor x\rfloor_a=\lceil x\rceil_a=0$ if $x$ does not contain $a$. Is the following language regular? $$L = \{x \in \{a, b\}^* \mid \lceil x\rceil_a - \lfloor x\rfloor_a \le 10 \}$$ Exercise 2. Is the following language regular? $$L = \{xy \mid x,y\in \{a,b\}^* \wedge ||x|_a - |y|_a| \leq 10 \}$$

  • $\begingroup$ sorry I hurry up and I wrote wrong task. I change now. $\endgroup$ – PoliteMan Feb 11 at 23:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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