0

Given the following Deterministic Finite Automata, I have to be able to tell what language the Automata accepts.image here]

As I can see, it accepts the letters a, b and c. Furthermore, my guess would be that it accepts words such as abca; abc. However, I have no idea how to tell what the "Language" of the Automata is/what language the automata recognizes. Is there any way to generally recognize the language the automata operates with? and what language would it be in this case?

Anonymous
  • 3

2 Answers2

0

The "language" (input symbols) is formally called an "alphabet".

Generally if only the graph such as your example is given, we assume that the alphabet comprises the symbols on top of the arrows. (Since even if other symbols are accepted, they would not do anything)

Formally, a DFA is a 5-tuple $(Q, \Sigma, \delta, q_0,F)$, where $\Sigma$ is the alphabet. Therefore given a formally defined DFA, we would have the alphabet it recognizes.

player3236
  • 16,413
0

The basic idea is that accepted words (on alphabet $\{a,b,c\}$) have to reach $q_2$ starting from $q_0$. As @player3236 says, you're mixing the alphabet (the letters the automaton works on) and the recognized language (the words on the alphabet that end up in an accepting state).

For instance, when reading the one letter word $a$ (from $q_0$), we reach $q_1$, which is not an accepting stqte, hence $a$ is not an accepted word.

That's even worse for words $b$ and $c$, since there is no arrow labelled with these letters from $q_0$ these words are not accepted either.

Hence, you know that an accepted word has to start with letter $a$. Let's check the two letter word $ab$: $q_0\xrightarrow{a}q_1\xrightarrow{b}q_1$ is not accepted, while $ac$: $q_0\xrightarrow{a}q_1\xrightarrow{c}q_2$ is (since it ends in $q_2$).

From this, if you take a few more examples, you should be able to understand what is the accepted language.

thibo
  • 821