I need clarification about DFA's and DFA acceptable languages

Question

In class yesterday we went over DFA's and DFA acceptable languages. An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$. The reason given was that the machine would need an infinite amount of states.

But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?

Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states. But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

I think I must be misunderstanding something crucial here.

Answer 1

$Doubt-1$: "But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?"

No, the DFA you are thinking about as below: accepts $(a + b)^*$ that is "all possible string consists of symbols '$a$' and '$b$', including $ε$ string".

     __
     ||  a, b
     ▼| 
––►((Q0))

Q0 is both initial and final state

Language accepted by this DFA is superset of language $L = \{ a^nb^n$ | $n > 0 \}$ and hance also accepts all strings in $L$.

The concept you are missing is: "An automata $A$ for some language $L$ must accept $\textit{exactly}$ language $L$, neither a subset nor a superset of $L$".

Hance DFA above is not a finite representation of language $L = \{ a^nb^n$ | $n > 0 \}$.

$Doubt-2$: "Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states".

Note: To construct new complement DFA $D$, old-DFA $A$ must be a complete, means there should all possible outgoing edge from each state (or in other words δ should be a complete function). Read "Complement DFA for Regular Expression $(00 + 1)^*$" to learn how to consturct complement DFA.

$Doubt-3$: But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

As you already know complement of a regular language is regular (DFA exists for regular language and you know how to make DFA for complement regular language), so new language $L^" $ = $\{ a, b \}^* - \{ a \}$ is a regular language.

And language $L^" $ is a superset of language $\{ a^nb^n$ | $n > 0 \}$.

The concept you are missing is that you don't know:

$Doubt-4$: "What is called regular language?" And Why a languages like $(a + b)^*$ is regular? But language $\{ a^nb^n$ | $n > 0 \}$ is not a regular language**

A language (a set) $L$ is called Regular Language, if its require bounded (finite) amount of information at any instance of time while processing a strings in language $L$.

What is bounded information?
For example: Consider a fan switch for on-off. By viewing fan-switch we can say whether fan is in on or off state (this is bounded or limited information).
But we can not know that how many times a fan has been on-off in past! (to memorized, it requires a mechanism to store unbounded amount of information to count how many times – e.g. some kind of meters, we have in our car/bike).

To understand how states are uses as memory element read this answer, you may also like to read: How to write regular expression for a DFA

Language $\{ a^nb^n$ | $n > 0 \}$ is not a regular because here $n$ is unbounded. To verify string in language $a^nb^n$ we have to remember how many '$a$' has been came and this required a infinite memory to count because number of '$a$' s in string that can be infinity large.
(hence an automata can only capable to process strings of $a^nb^n$ if it has infinite memory e.g PDA).

Whereas $(a + b)^*$ is of-course a regular by its nature, because there is bounded restriction that "string consists of only symbol '$a$' and '$b$'". And strings of this language can be easily processed (or recognized) by an automata in which we have finite memory that is finite automata. Yes, in finite automata we have finite memory in terms of states (The word "Finite" significance of the presence of 'finite amount of memory' in the form of finite number of states $Q$).

Summarize:

Memory in finite automata is present in the form of states $Q$ only and according to automata principal: any automata can have only finite set of states. hence finite automata has finite memory, this is the reason automata for regular language is called finite automata. You can think a finite automata like CPU without memory, that has finite register to remember its internal states.

Finite State –► Finite Memory –► Only language can be process for which finite memory need to store at any instance of time while processing the string: –► that language is called Regular Language

Absence of external memory is limitation of finite automate –► or we can say limitation of class of language defined by finite automata that is called Regular language.

Side note::
* Also a language { aⁿbⁿ | 10^>100 n > 0 } is regular, a large set but regular because $n$ is bounded, hence finite automata and regular expression is possible for this language – finite set is always regular. * There are infinite sets those are regular. Regular language of subset of all possible infinite set. Check this Venn-diagram.

So, if any time you need to proof that a language $L$ not a regular – before the go to use "formal tools" likes pumping lemma, first try to proof using fundamental definition of regular language.

Answer 2

Let me summarize the answers given in the comments to the question.

An automaton $A$ accepts a language $L$ if it accepts each word in $L$ and rejects each word not in $L$. Each automaton $A$ accepts a unique language $L$ which consists of all words accepted by $A$. Therefore, while the one-state automaton accepting $\{a,b\}^*$ does accept all the words in $L = \{a^n b^n : n \geq 0\}$, it does not accept $L$ since it also accepts other words such as $b$.

For completeness, here is the proof that an automaton for $L$ would require infinitely many states, or more formally, that no DFA accepts $L$. Suppose there was some DFA $A$ accepting $L$. Let $s_n$ be the state that $A$ is in after reading $a^n$. I claim that $s_n \neq s_m$ for all $n \neq m$. Indeed, starting at $s_n$ and reading $b^n$, the automaton $A$ ends up in an accepting state since $a^n b^n \in L$. If $s_m = s_n$ then this means that $A$ would accepts $a^n b^m \notin L$. This contradiction shows that $s_n \neq s_m$ for all $n \neq m$, and so $A$ must contain infinitely many states, which it can't since DFAs have finitely many states. So no DFA accepts $L$.

For a generalization, check out the Myhill–Nerode theorem.

Answer 3

Acceptance of a Language $L$(regular): means there is a finite accepter that accept all strings $w$ belongs to L and reject all strings not in $L$.

An example of a language that is not DFA acceptable is $L=\{ab,aabb,aaabbb,aaaabbbb,…\}$.The question is why: there can be a finite accepter for all the strings w belongs to L but that finite accepter can also accept those strings that do not belong to L. So according to the definition of acceptance, there can't be a finite accepter for $L$.

Finite accepter (DFA and NFA) can't accept these language because to accept these kind of languages the machine need infinite memory to store number of $a$'s and $b$'s(Since number of a and b is unbounded, we require storing an unbounded amount of information). But Finite automata do not have temporary storage capability. There is a more capable Automata named Pushdown Automata that can recognize this language.(This language is known as context free language)

The language $L=\{a\}$ is definitely DFA acceptable because there can be a finite accepter that only accept the string $a$. But complement of $L$ not only includes $ab,aabb,aaabbb,…$ these strings. It also includes strings $b$, $aab$, $abb$,$aabbb$ etc. And simply by swapping the final states and the non-final states of the DFA for $L$ you can get a finite accpter that accepts the language which is complement of $L$ .