CODEWITHSUNDEEP
computation-theory
gaurav bhardwaj
gaurav bhardwaj

Reputation: 21

a finite automaton only rejects a finite number of strings

Does a finite automaton always reject the finite number of String? In my view when an automaton can accept the infinite number of string in the same way it can also reject the infinite number of strings. please give proof also.

Upvotes: 1

Views: 524

Answers (1)

Patrick87
Patrick87

Reputation: 28302

A DFA either accepts or rejects strings. It can:

  1. accept infinitely many strings and reject infinitely many strings; or
  2. accept infinitely many strings and reject finitely many strings; or
  3. accept finitely many strings and reject infinitely many strings.

A DFA cannot accept finitely many strings and reject finitely many strings simultaneously, since over any alphabet there are infinitely many strings and the DFA must either accept or reject every one of them.

Example of case 1: any DFA for the regular language (00)* = {e, 00, 0000, ...} over alphabet {0}. It accepts {e, 00, 000, ...} and rejects {0, 000, 00000, ...}.

Example of case 2: any DFA for the regular language 0+ = {0, 00, 000, ...} over the alphabet {0}. It accepts {0, 00, 000, ...} and rejects {e}.

Example of case 3: any DFA for the regular language {e} over the alphabet {0}. It accepts {e} and rejects {0, 00, 000, ...}.

Upvotes: 2

Related Questions