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