0
$\begingroup$

Just a quick question about regular languages and which NFAs accept them: If I were to draw an NFA that accepts a particular regular language, does that mean the NFA can only accept strings in that language or can the NFA accept every string in that language and some extra ones?

For example, for the regular language a+ ∪ (ab)+ (given as a regular expression) the corresponding NFA that I drew looks like this:

enter image description here

This NFA would accept any string in the given regular expression (a, aa, aaa, ab, abababab, etc) but it would also accept some extra strings that aren't in the expression (aba, aaaab, aaabab, etc). Would the NFA be correct because it includes every string in the regular expression? Or would it be incorrect because it includes some strings that aren't in the expression? Any and all advice is much appreciated. Thank you!

$\endgroup$

2 Answers 2

1
$\begingroup$

The language of an NFA $A$, denoted $L(A)$, is the set of words $w$ such that there is an accepting run of $A$ on $w$. Hence, when we claim that an NFA $A$ recognizes a language $L$, we mean that $L(A) = L$, and by that we mean equality of sets, that is, we have two-sided containment:

(1) $L(A)\subseteq L$: every word $w$ that $A$ has an accepting run on is such that $w\in L$.

(2) $L\subseteq L(A)$: $A$ has an accepting run on every word in $L$.

What you did is a suggestion of an NFA that satisfies only condition (2) w.r.t your language. It does not make sense, and it is also not hard to obtain such an NFA: an NFA that accepts all inputs has a language that includes all other languages. So yes, your solution is incorrect as it does not recognize the language of the regular expression -- condition (1) does not hold, your NFA accepts more words than it should.

$\endgroup$
0
$\begingroup$

The "corresponding NFA", as you call it, for $a^+ ∪ (ab)^+$ is not your $$→ q_0,\quad q_0 \overset{a}→ q_0,\quad q_0 \overset{a}→ q_1,\quad q_1 \overset{b}{→} q_2,\quad q_1 →,\quad q_2 → q_0,\quad q_2 →,$$ but this $$→ q_0,\quad q_0 \overset{a}→ q_1,\quad q_0 \overset{a}→ q_2,\quad q_1 \overset{b}→ q_3,\quad q_2 \overset{a}→ q_2,\quad q_2 →,\quad q_3 \overset{a}→ q_1,\quad q_3 →.$$

Your NFA corresponds to the regular expression $(a ∪ ab)^+$, and it could just as well be written as this $$ → q_0,\quad q_0 \overset{a}→ q_1,\quad q_0 \overset{a}→ q_2,\quad q_1 \overset{b}→ q_2,\quad q_2 → q_0,\quad q_2 →. $$

$\endgroup$

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.