$L = \{y \in (a+b)^* \mid ||y|_a - |y|_b| \leq 10 \}$
Any idea? I have problem with this kind of task.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Have you studied the reference question and answers How to prove that a language is not regular?? $\endgroup$– John L.Commented Feb 11, 2019 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. ♦Commented Feb 11, 2019 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$– John L.Commented Feb 11, 2019 at 23:38
-
$\begingroup$ @Apass.Jack yes $\endgroup$– PoliteManCommented Feb 11, 2019 at 23:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$ Commented Feb 11, 2019 at 23:25