1

When we define:
$δ:(Q \timesΣ\to2^Q)$
$2^Q$ represents the numbers of transitions or the resulting position after the automaton get letter?

postFix
  • 257

1 Answers1

1

$2^Q$ encodes the subset of $Q$ that are active after evaluating the input string. If there are states $Q_1, Q_2, Q_3, ...$ then examples of elements of $2^Q$ are $<yes, no, yes, yes, no,...>$ which can also be written $<1, 0, 1, 1, 0,...>$ where $yes$ or $1$ represents that state being active after the string is evaluated.

John_Krampf
  • 416
  • 2
  • 12
  • so if I understand correctly we use $2^Q$ and not $3^Q$ (for example) because we want to say that any state can be active or not? – postFix Mar 12 '21 at 17:52
  • Correct. If there were a third option, like active, not active, and ??? then it would be $3^Q$. When I think about it, it's a confusing notation. $2^Q$ means ${0, 1}^Q$ i.e. ${0, 1} \times {0, 1} \times {0, 1} \times ...$ $Q$ times (once for each possible state) – John_Krampf Mar 12 '21 at 17:54
  • 1
    Thanks, it really helped me to put things in order :) – postFix Mar 12 '21 at 18:05