2
$\begingroup$

How would you write the language for this DFA as L(M) = {...}?

I think in English I would say L(M) is defined as {a,b}* ending in b, ba or aa.

a simple DFA

  • 0
    No, because every word in the language must have an even number of $a$’s.2011-09-16

3 Answers 3

5

There are two kinds of non-empty word that go from $q_0$ to $q_0$ without passing through $q_0$ again along the way. One is the word $b$, and the other is any word of the form $ab^*a$. Any number of words of these two types can be concatenated in any order, so the language is that given by the regular expression $(b\mid ab^*a)^*$. In terms of sets that’s $\left(\{b\}\cup \{a\}\{b\}^*\{a\}\right)^*$.

If you look closely at this, you’ll see that it can be matched to any word that contains an even number of $a$’s: match any initial $b$’s to $b^*$, then match the first two $a$’s and any $b$’s between them to $ab^*a$, and repeat as needed, matching any trailing $b$’s to $b^*$. Conversely, any word in the language clearly must contain an even number of $a$’s in order to drive the DFA to $q_0$. Thus, the language can be expressed very simply in English: it’s the set of words over $\{a,b\}$ containing an even number of $a$’s.

  • 0
    Thank you. I never considered unions. Looks like my English definition is wrong too. I'll go over that subject again.2011-09-16
0

I will asume like Gerry Myerson that $q_0$ is the starting state and the only accepting state. I think the set of strings with even number of $a$'s is the accepted language of this DFA. The $b$'s will only keep you in the current state and the $a$'s move you to the other state. You are in state $q_0$ if and only if the number of $a$'s is even.

0

Its the language of even number of $a$'s.

Remember $0$ $a$'s is still an even number of $a$'s.