1
$\begingroup$

Consider the alphabet E = ${[abc] : a, b, c \in 0,1,...,9)} $ Example [234], [567], [897] are symbols of the alphabet. For a string $w \in $ let n(w) denote the number represented by $ w $: Example for symbol [345], n([345]) = 345.

1) Describe a DFA for the language of strings of the form $[x_0y_0z_0][x_1y_1z_1] [x_ny_nz_n]$ such that

$n(x_n... x_1x_0) + n(y_n... y_1y_0) = n(z_n... z_1z_0)$

This language corresponds of reading the numbers from right to left and position by position; this is how we add numbers by hand.Example $[819][606][213]$ is in the language because 268 + 101 =369.

How can we describe something like this? $M = (Q, E, d, q_0, F)$

where Q : ?

E = ${[abc] : a, b, c \in 0,1,...,9)} $

d: ?

$q_0 = $

F: ?

$\endgroup$
  • $\begingroup$ Normally, what you would do is just "draw the DFA", as you put it. It is not always practical to do so - for instance, it may be too big. In these cases, what you do is describe how would you draw it, like an algorithm. $\endgroup$ – André Souza Lemos Apr 6 '16 at 22:50
  • $\begingroup$ hmmm so in general we can use the M = (Q, E, d , q_0, F) to describe it? $\endgroup$ – Darkflame Apr 6 '16 at 22:53
  • 2
    $\begingroup$ Try to understand why your teacher (I suppose you are a student) has given you the exercise. Use your creativity. $\endgroup$ – André Souza Lemos Apr 6 '16 at 23:16
  • 2
    $\begingroup$ So you basically ask what does it mean to describe DFA? why the long story attached to it? describing a DFA, is either (1) writing the formal 5-tuple, or (2) drawing the "state machine", or (3) describing in words what the DFA does. In "tests", way (1) and (2) are usually accepted, but its up to your professor. Consider editing the question to reflect what you really want to ask. $\endgroup$ – Ran G. Apr 7 '16 at 0:34
  • 1
    $\begingroup$ Then talk to your teacher and/or get a book. Seriously. The internet is not a good place to ask people if you don't even know what the task is. (And yes, plenty of people know how to start and still post here -- because then they can ask a real question.) Your question is similar to a person asking "how to solve this problem in Java?" when they don't know any Java. $\endgroup$ – Raphael Apr 7 '16 at 20:08
1
$\begingroup$

Notice that it's not unreasonable to slightly extend this problem to an arbitrary number of triples. For example, the single triplet [123] is a reasonable candidate to be in your language, since $1+2=3$. Similarly, [280][135] is another reasonable candidate, since $12+38=50$. With that in mind, I'll extend the language to all strings of an arbitrary number (including zero) of triples that satisfy the summation requirement. I'll also decide that we'll accept a sequence of triplets only if they represent a sum without a final carry, so we wouldn't accept the string [000][000][190] since $100+900=1000$ and there's a final carry out (though [000][000][190][001] would be accepted).

The fundamental idea is a very common one: "remember" the current state of the problem by using one state in the DFA for each possible configuration. Here's what we might do:

  1. Label the start state $start$. We haven't read any input yet. This will also be the unique final state.
  2. Let state $t$ remember that we've seen the first [, so we have the move $\delta(start, [)=t$.
  3. Next, construct ten states $p_0, p_1, \dotsc,p_9$ to remember the first digit. We'll have the moves $\delta(t,i)=p_i$, i.e., from $t$ we'll be in state $p_i$ after having seen input $i$.
  4. Now make twenty more states, $q_0, \dotsc,q_9$ and $c_0,\dotsc,c_9$. The $q$'s will record the sum of the first two inputs if there's no carry and the $c$'s will record the sum if there is a carry. In other words $$ \delta(p_i,j) =\begin{cases} q_{i+j} &\text{if } i+j\le 9\\ c_{(i+j)\bmod{10}} &\text{if } i+j\ge 10 \end{cases} $$
  5. Then make two states, $a,b$ to note whether the third input is the sum of the first two and wehther or not we've generated a carry. From state $q_k$ (sum is $k$ with no carry) we'll pass to state $a$ if the third input is the digit $k$. Similarly, we'll have $\delta(c_k,k)=b$ meaning that we've just seen the appropriate third digit and we had a carry.
  6. Now we've read the first triplet and we're expecting to see a ]. In state $a$ we know we've completed the first triplet and don't have to adjust any subsequent triplet, so $\delta(a,]) = start$, i.e., we loop back to the start and accept if there's no further input. On the other hand, if we're in state $b$ then we have a correct digit sum, but we also have a carry, so we can't yet accept when we see a ], instead we need to read another triplet. We'll process the ], read a [ and duplicate the whole process again, this time adjusting for the carry. We'll then have $\delta(b, ])=u$ and $\delta(u,[)=v$.
  7. Starting anew from state $v$, we construct 34 new states exactly as we did in steps (1) - (6). The only difference is that the transitions from the new states corresponding to the original $p$ states (call them $p'_i$) in step (4) we'll compensate for the previous carry in and have $$ \delta(p_i,j) =\begin{cases} q_{i+j+1} &\text{if } i+j+1\le 9\\ c_{(i+j+1)\bmod{10}} &\text{if } i+j+1\ge 10 \end{cases} $$ The final difference with these new states is that if we get to the new state, $b'$ corresponding to the original $b$, then on seeing ], we go back to state $start'$ and start again.

In high-level terms, we have two nearly-identical functions to check whether a triplet $t$ is valid:

  • $N(t)$ which checks whether $t$ is valid, assuming no carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.
  • $C(t)$ which checks whether $t$ is valid, assuming a carry in. This will return 0 or 1, depending on whether or not $t$ generated a carry.

Then, we would have the following pseudocode

c = 0
while there's a triplet t to process
   get t
   if c = 0
      c = N(t)
   else
      c = C(t)
end loop
if c = 0
   accept
else
   reject
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.