0
$\begingroup$

I have to construct NFA that accepts language $L=\{wbbav \;|\; w \in \{a,b\}^*, v \in \{a,b\}^+, v\; has\; suffix\; a\}$.

My solution is this automata:

My automata

Can you tell me, if this is correct or not? If yes, it is possible to construct this NFA with less states?

$\endgroup$
6
  • 1
    $\begingroup$ Isn't the regular expression is just (a|b)*bba(a|b)*a? $\endgroup$
    – rnbguy
    Apr 9, 2018 at 13:14
  • 1
    $\begingroup$ You can remove the middle self-loop if you wish. $\endgroup$ Apr 9, 2018 at 13:15
  • $\begingroup$ Sorry but we're here to answer questions about computer science, not to grade solutions to exercises. It might help if you think about why you're not certain if your answer is correct and ask a question about that. Then, you'll be able to figure out if your solution is correct and the explanation might be useful to others in thefuture. $\endgroup$ Apr 9, 2018 at 13:19
  • $\begingroup$ ^ keeping this mind -- you can use subset construction to check the correctness of the regular expression. $\endgroup$
    – rnbguy
    Apr 9, 2018 at 13:21
  • $\begingroup$ @YuvalFilmus his question is, can this NFA recognize the language? It's not now to make it correct/efficient. :) $\endgroup$
    – rnbguy
    Apr 9, 2018 at 14:22

1 Answer 1

2
$\begingroup$

I will address your second question, namely, whether there is an NFA with fewer states. The appropriate technique here is fooling set:

Let $L$ be a language, and let $x_1,\ldots,x_n,y_1,\ldots,y_n$ be words such that $x_iy_i \in L$ but for every $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. Then every NFA for $L$ contains at least $n$ states.

(The proof is a simple exercise.)

In our case, we take $$ \begin{array}{c|cc} i & x_i & y_i \\\hline 1 & bbaa & \epsilon \\ 2 & bba & a \\ 3 & bb & aa \\ 4 & b & aaa \\ 5 & \epsilon & bbaa \end{array} $$ For all $i$ we have $x_iy_i = bbaa \in L$. Conversely, if $i < j$ then $|x_jy_i| < 4$ and so $x_jy_i \notin L$.

In fact, we have proven the following more general result:

If the minimal length of a word in $L$ is $\ell$, then every NFA for $L$ contains at least $\ell+1$ states.

$\endgroup$
1
  • $\begingroup$ thank you for your answer. from your answer I get, that my automata is correct and has minimal count of states. $\endgroup$
    – Johny
    Apr 9, 2018 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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