1

Why is this the $L(M)$ of this DFA? Can someone please explain it? I am new to this course. When I tried alone answering the question of "What is special about the words that get accepted by this DFA?" I answered that "any word that ends with a while the letter before it is not a ($\epsilon a$ for example or $ba$ or...."

enter image description here

TheNotMe
  • 4,841

3 Answers3

2

First of all note that your DFA accepts the string $\newcommand{\aa}{\mathtt{a}}\newcommand{\bb}{\mathtt{b}}\aa\aa\aa$, so your characterisation of the language it accepts is a bit off.

Hint. An inspection of the DFA reveals the following simple facts:

  1. Reading an $\aa$ from either $q_1$ or $q_3$ brings you to the accepting state.
  2. Reading a $\bb$ from either $q_1$ or $q_3$ brings you to the opposite state.
  3. Reading either an $\aa$ or a $\bb$ from the accepting state $q_2$ brings you to one of $q_1$ or $q_3$.

Concentrate first on the ways you can get from the accepting state back to itself (in particular by only reading consecutive $\aa$s), and then note that the only way to get from a non-accepting state to the accepting state is to read an $\aa$.

user642796
  • 52,188
0

Hint. Your automaton is deterministic but it is not minimal. First compute its equivalent minimal DFA and your problem will become much simpler.

J.-E. Pin
  • 40,163
0

Language of automaton is just list of transitions (from where to where by each input character as we read), You've listed the list as a Regular Expression (RE). RE is just showing what should be accepted by this particular automaton not showing what the actual implementation is.

The Language is SUM of transitions:

Start State : q1

End State   : q2

$\delta (q1,a) = q2$

$\delta (q1,b) = q3$

$\delta (q2,a) = q1$

$\delta (q2,b) = q3$

$\delta (q3,b) = q1$

$\delta (q3,a) = q2$

This is the basic of Theory of Computation course, I highly recommend watch tutorials or read more to concretely understand this basics.

Node.JS
  • 1,119