I need clarification about DFA's and DFA acceptable languages

Problem Detail: 

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.

Asked By : tAllan

Answered By : Grijesh Chauhan

$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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23460