The language is this:
$L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$
This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, right?
$\begingroup$
$\endgroup$
-
3$\begingroup$ What do you mean by "matching"? Do you mean the number of $a$ is no more than the number of $b$? $\endgroup$ – xskxzr Sep 27 '19 at 4:01
-
$\begingroup$ Possible duplicate of How to simulate backreferences, lookaheads, and lookbehinds in finite state automata? $\endgroup$ – Evil Sep 27 '19 at 13:19
-
$\begingroup$ Or do you mean: a bijective mapping can be constructed between the $a$s and the $b$s? (In other words, the number of $a$s and $b$s is equal.) $\endgroup$ – reinierpost Oct 3 '19 at 17:53
$\begingroup$
$\endgroup$
Expanding on Daniel Martin's answer. None of the following interpretations yields a regular language:
- $L = \{ w \in \{a,b\}^* : \exists n \ge 0, \; w = a^n b^n \}$
- $L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$.
- $L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is equal than the number of $b$s in $w$.
- $L$ contains all the words $w \in \{a,b\}^*$ such that there is a injective/bijective mapping that maps each a $a$ that appears in a generic position $i$ in $w$ with a $b$ in $w$ that appears in a position $j>i$.
The proof is the same for all cases: if $L$ was regular then, for a sufficiently large $n$, the word $w = a^n b^n \in L$ could be written as $w = a^{n-k} a^k b^n$ (with $1 \le k \le n)$ in such a way that $a^{n-k}a^{k \cdot h} b^n \in L$ for all choices of $h \in \mathbb{N}$ (see pumping lemma for regular languages). This is a contradiction since $a^{n-k}a^{2k} b^n = a^{n+k}b^{n} \not\in L$.
$\begingroup$
$\endgroup$
As the comments say, it isn't completely clear what you mean by "matching", but if you mean that for any positive integer $n$, the string $\mathtt{a}^n\mathtt{b}^n$ (that is, the string of $n$ "$\mathtt{a}$"s followed by $n$ "$\mathtt{b}$"s) is in the language, but $\mathtt{a}^n\mathtt{b}^{n-1}$ is not in the language, then what you say is correct: $L$ is not a regular language because you would need an infinite number of states, at least one for every string of the form $\mathtt{a}^n$.
