1,507 views
1 votes
1 votes

Find an NFA with two states that accepts the following language:

L = {an : n ≥ 1} ∪ {bmak : m ≥ 0, k ≥ 0}.

1 Answer

2 votes
2 votes

$\{a^n : n \geq 1\}$ is a subset of $\{b^ma^k : m \geq 0, k \geq 0\}$.

So, their union will be : $\{b^ma^k : m \geq 0, k \geq 0\}$

Since, the question is asking for an NFA, we do not need to draw all transitions. So, here it is:

The missing links lead to a dead state.

Related questions

0 votes
0 votes
0 answers
1
koushriek asked May 19, 2022
1,281 views
Examples of accepted words: 1011, 101101, 1111Example of non-accepted words: 101, 1001, 010The solution says the min-DFA contains 5 states but I could only do it in 4. Am...
4 votes
4 votes
1 answer
2
Aakanchha asked May 22, 2015
5,094 views
Build an FA that accepts the language of all strings of a's and b's such that next-to-last letter is an $a$.