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

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

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

• Have you studied the reference question and answers How to prove that a language is not regular?? – Apass.Jack Feb 11 at 22:08
• 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. – D.W. Feb 11 at 23:28
• 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? – Apass.Jack Feb 11 at 23:38
• @Apass.Jack yes – PoliteMan Feb 11 at 23:42

## 1 Answer

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

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