0
$\begingroup$

I was trying to solve these two questions for a while, can I know how can I use pumping lemma to solve them?

a) $\{a^i b^j \mid i, j \geq 0 \text{ and }i + j = 5\}$.

b) $\{w = xy \mid x, y \in \{a, b\}^* \text{ and } |x| = |y| \text{ and } \#a(x) \geq \#a(y) \}$.

and thanks

$\endgroup$
3
  • $\begingroup$ Welcome to SE network, please visit Help Center $\endgroup$
    – ً ً
    Jan 5 '17 at 13:44
  • $\begingroup$ Did you really try seriously to solve a) ? $\endgroup$
    – J.-E. Pin
    Jan 5 '17 at 14:00
  • $\begingroup$ @J.-E.Pin I did try and I solve it, I found similar question but with (i doesn`t equal j) $\endgroup$
    – rain ss99
    Jan 7 '17 at 15:44
1
$\begingroup$

Language a) is regular.

To see this, observe that there are only finitely many strings in this language (all strings of length $5$ such that the string is composed of zero or more $a$s followed by zero or more $b$s). Thus, we can compose a DFA, which has a finite number of accepting states corresponding to these strings, and all other states are not accepting. In general, any finite language is regular.

Language b) is not regular.

To see this, we need to use the pumping lemma. Suppose language b) was regular, and was the language corresponding to some DFA $D$, which has $N$ states. The pumping length of this language must be $\leq N$.

Clearly, $w = b^{N+1}ab^{N+1}a$ is part of this language. Using the pumping lemma on $w$, we need to decompose $w=xyz$, where $|xy|\leq N$ and $|y|\geq 1$. The only way this can happen is if $y=b^i$ for some $i\geq 1$. Then, by pumping $w$, we see that $xy^2z=b^{N+1+i}ab^{N+1}a$ must be in this language, but it is not as the first half of the language contains only $b$s but the second half has at least one $a$.

This is a contradiction, and hence the assumption that language b) was regular is false.

$\endgroup$
2
  • $\begingroup$ can you help me in composing the dfa? because I should use pumping lemma first to prove then draw the dfa if it`s possible $\endgroup$
    – rain ss99
    Jan 7 '17 at 15:49
  • $\begingroup$ + isn`t this the same as my question, L = {a^ib^j: i, j >= 0 and i not equal j} $\endgroup$
    – rain ss99
    Jan 7 '17 at 15:52

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.