I've been trying to create a NFA that accepts strings that end with a letter that exists in the string. For example abcdb, cbdd, acac etc. while strings like abc aacd etc are not accepted since the last letter wasnt in the string before the last letter was read. I only seem to be able to create a NFA that accepts a subset of the language. What is the right way to go about it? I'm very lost. enter image description here

This is my try at a 2 letter alphabet but i feel like for a 4 letter alphabet the NFA is going to be huge. Is there a methodology I'm completely missing or do I just use brute force?

  • $\begingroup$ Does it help if you try to do the same for the alphabet $\{a,b\}$ first? Then it is straight-forward to add the rest of the characters. $\endgroup$ – frabala Apr 21 '20 at 13:36
  • $\begingroup$ Had a go at it but it just seems like the number of states will grow way too much for a 4 letter alphabet. Could there be any other way? $\endgroup$ – Evan Shini Apr 21 '20 at 15:28
  • $\begingroup$ Remember you are building an NFA, not a DFA. You can consider many possibilities at once. You need four accepting states, one for each character. Every accepting state $q_x$ must have a path from the initial state and this path must guarantee that $x$ is the last symbol of the input and has appeared once more before its last occurence. $\endgroup$ – frabala Apr 21 '20 at 17:30

The idea is to implement the following regular expression: $$ \sum_{\sigma \in \Sigma} \Sigma^* \sigma \Sigma^* \sigma. $$ Details left to you. Number of states is $|\Sigma| + 2$.

Let us show that $|\Sigma| + 2$ is the optimal number of states, using the fooling set method. We have to give $|\Sigma|+2$ pairs $(x_i,y_i)$ such that $x_iy_i \in L$ (here $L$ is your language), but for each $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. For each $\sigma$, we have the pair $x_\sigma = y_\sigma = \sigma$. For some arbitrary $\tau \in \Sigma$, we have the two pairs $x_\gets = \tau\tau, y_\gets = \epsilon$ and $x_\to = \epsilon,y_\to = \tau\tau$. You can check that indeed $x_iy_i \in L$ for all $i$. In the other direction:

  • If $\sigma_1 \neq \sigma_2 \in \Sigma$ then $x_{\sigma_1} y_{\sigma_2} \notin L$.
  • If $\sigma \in \Sigma$ then $x_\sigma y_\gets, x_\to y_\sigma \notin L$.
  • Similarly, $x_\to y_\gets \notin L$.

Your automaton is correct. You could merge states $q_5$ and $q_4$ into one state that has a loop for both symbols $a$ and $b$. Same for states $q_8$ and $q_9$.

However, you automaton is a DFA. It does not make use of an NFA's non-determinism. That's why it doesn't easily scale for bigger alphabets and it grows exponentially.

In simple words, non determinism means that there can be more than one outgoing transitions from a state for the same symbol (plus, there are ε-transitions). Then the NFA accepts iff at least one of all the possible paths accepts.

For your automaton, assuming binary language $\{0,1\}$, if you use non-determinism, you need only two accepting states $a_0$ and $a_1$, the initial state $s$ and two more states $q_1$ and $q_2$.

  1. The accepting states have no outgoing transitions.
  2. Add transitions $q_i\stackrel{i}{\to}a_i$, for $i=1,2$. These transitions represent the last step taken by the machine when reading the last symbol of an input for which the machine should accept. If the machine is in state $q_i$, it means that the string should end with symbol $i$.
  3. But to accept a string ending with symbol $i$, this symbol must have appeared before in the string. So, if the machine is in state $q_i$ it should also mean that symbol $i$ has already appeared in the string. Add transitions $s\stackrel{i}{\to}q_i$. Now, the machine accepts the simplest words that satisfy the condition: 00 and 11.
  4. However, if there's any string prepended in 00, or if there's any string between the two 0s, or if both cases are happening, the machine should still accept the string. Same for 11. For that reason you also need to add loops $s\stackrel{i}{\to}s$ and $q_i\stackrel{j}{\to}q_i$, for $i,j = 1,2$.

Do you see how to scale this for an alphabet of size 4?


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.