7. Language of a DFA

Language of a DFA

Language

A language (over an alphabet $S$) is a set of words over $S$.

For example, given $S=\{a,b,c,...,z\}$.

• $L_1=\text{ all English words}$
• $L_2=\text{ all Latin words}$
• $L_3=\{ghgkrf,oputj,erwwq\}$

Given $S=\{0,1\}$:

• $L_4=\{001,101010,111,1001\}$
• $L_5=\{0^n{1}^m|n\text{ is even},m\text{ is odd}\}$

Link to original

Language of a DFA

A DFA may accept certain words, while may reject others. If we collect all words accepted by a DFA $A$, we obtain a language: the language of a DFA $A$ is: ?

$$L(A)=\text{set of all words over its input alphabet that }A\text{ accepts}$$Link to original

Example

Using 4. State transition diagrams > Automaton A_1 (hover for preview), we already know:

• That $aabb$ and $bbb$ are accepted.
• That $abba$, $bbaaa$ and $ϵ$ were rejected.

Hence, $L(A_1)=\text{all the words starting with some (potentially none) }a\text{ s followed by at least one }b$.

$$\begin{array}{rl}L(A_1)& =\{a^n{b}^m|n=0,1,2,...,m=1,2,...\}\\ & =\{a^n{b}^m|n\in \mathbb{N},m\in {\mathbb{N}}^{+}\}\end{array}$$

Finding the language of a finite automaton

1. Experiment with words.
2. Come up with a language.
3. Test the suggested language:
   • every word that is accepted by the automaton should be in the suggested language
   • every word that is rejected by the automaton must not be in the suggested language
4. Revise the suggested language if necessary, then go to step 3.