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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityThe 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?
Expanding on Daniel Martin's answer. None of the following interpretations yields a regular language:
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$.
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$.