Finite Automata

Language Accepted by DFA



Subjects to be Learned

Contents

Here we are going to formally define what is meant by a DFA (deterministic finite automaton) accepting a string or a language.

A string w is accepted by a DFA   < Q , , q0 , , A > ,   if and only if     *( q0 , w ) A . That is a string is accepted by a DFA if and only if the DFA starting at the initial state ends in an accepting state after reading the string.
A language L is accepted by a DFA   < Q , , q0 , , A > ,   if and only if     L = { w | *( q0 , w ) A } . That is, the language accepted by a DFA is the set of strings accepted by the DFA.


Example 1 :




This DFA accepts {} because it can go from the initial state to the accepting state (also the initial state) without reading any symbol of the alphabet i.e. by reading an empty string . It accepts nothing else because any non-empty symbol would take it to state 1, which is not an accepting state, and it stays there.

Example 2 :

                                   



This DFA does not accept any string because it has no accepting state. Thus the language it accepts is the empty set .

Example 3 : DFA with one cycle

                                   



This DFA has a cycle: 1 - 2 - 1 and it can go through this cycle any number of times by reading substring ab repeatedly.
To find the language it accepts, first from the initial state go to state 1 by reading one a. Then from state 1 go through the cycle 1 - 2 - 1 any number of times by reading substring ab any number of times to come back to state 1. This is represented by (ab)*. Then from state 1 go to state 2 and then to state 3 by reading aa. Thus a string that is accepted by this DFA can be represented by a(ab)*aa .


Example 4 : DFA with two independent cycles



                                   



This DFA has two independent cycles: 0 - 1 - 0 and 0 - 2 - 0 and it can move through these cycles any number of times in any order to reach the accepting state from the initial state such as 0 - 1 - 0 - 2 - 0 - 2 - 0. Thus a string that is accepted by this DFA can be represented by ( ab + bb )*.


Example 5 : DFA with two interleaved cycles



                                   



This DFA has two cycles: 1 - 2 - 0 - 1 and 1 - 2 - 3 - 1.
To find the language accepted by this DFA, first from state 0 go to state 1 by reading a ( any other state which is common to these cycles such as state 2 can also be used instead of state 1 ). Then from state 1 go through the two cycles 1 - 2 - 0 - 1 and 1 - 2 - 3 - 1 any number of times in any order by reading substrings baa and bba, respectively. At this point a substring a( baa + bba )* will have been read. Then go from state 1 to state 2 and then to state 3 by reading bb. Thus altogether a( baa + bba )*bb will have been read when state 3 is reached from state 0.


Example 6 :

                                   



This DFA has two accepting states: 0 and 1. Thus the language that is accepted by this DFA is the union of the language accepted at state 0 and the one accepted at state 1. The language accepted at state 0 is b* . To find the language accepted at state 1, first at state 0 read any number of b's. Then go to state 1 by reading one a. At this point (b*a) will have been read. At state 1 go through the cycle 1 - 2 - 1 any number of times by reading substring ba repeatedly. Thus the language accepted at state 1 is b*a(ba)* .


There is a systematic way of finding the language accepted by a DFA and we are going to learn it later. So we are not going to go any further on this problem here.



Next -- Definition of Nondeterministic Finite Automata


Back to Study Schedule


Back to Table of Contents