regular languages – Efficient algorithm to find a rejecting input of an NFA

I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.

The algorithm should have the following behavior: Given an NFA $A = (Q, Sigma, Delta, q_0, F)$, if $L(A) = Sigma^*$, then return the error state $Err$, otherwise return any $w in Sigma^* setminus L(A)$.

Ideally, $w$ should be as short as possible.

Is this possible?


What I tried:

I thought of using a modified version of Thompson’s algorithm. In Thompson’s algorithm, the current input character is used to determine the next set of states from the current set of states. Thompson’s algorithm will reject an input string if (1) the next set of states is empty or (2) if the string ended and the current set of states does not contain a final state.

Let $N_T: P(Q) times Sigma to P(Q)$ be the function from Thompson’s algorithm that given the current set of states and an input character determines the next set of states.

By repeatedly using all characters $c in Sigma$ as input characters to create the next set of states, the algorithm can approximate simulating all input strings. The function determining the next set of states is defined as:

$$N: P(Q) to P(Q); \ N(S) = bigcup_{c in Sigma} N_T(S, c)$$

The current set of states for a given iteration $k$ is defined as: $$S_k =
begin{cases}
{q_0}, & text{if } k = 0 \
N(S_{k-1}), & text{otherwise}
end{cases}
$$

In each iteration $k$, the following conditions (corresponding to the rejection conditions of Thompson’s algorithm) are checked:

  1. If $exists c in Sigma$ such that $N_T(c)=emptyset$, then all $w in Sigma^k c$ will be rejected by $A$. Return any $w$.
  2. If $S_k cap F = emptyset$, then all $w in Sigma^k$ will be rejected by $A$. Return any $w$.

Lastly, if an already seen set of states is seen again, the algorithm returns $Err$. This ensures that the algorithm terminates.

However, there are 2 problems with this algorithm:

  1. It’s only an approximation. There are some NFA for which this algorithm returns $Err$ even though the NFA doesn’t accept all inputs.
  2. It terminates after at most $2^{O(n)}$ many steps. This isn’t PTIME. However, this problem can be solved by only allowing $|Q|$ many iterations since the shortest rejecting input should have at most $|Q|$ many characters.

finite automata – NFA designing for strings starting with $01$

The question was asked

Construct an NFA with set of all strings that start with $10$.

The solution provided to me is
enter image description here

But my question is what if the automaton receives an input $0$ at the starting? Also there is no option for $q_1$ to transit after receiving $1$. So I think the solution should be

enter image description here

Please correct me if I am wrong.

finite automata – Does a DFA accepts all strings accepted by the Equivalent NFA?

I have been studying the conversion from an NFA to the equivalent DFA. And I came across this NFA

NFA with ∑ = {0, 1} accepts all strings with 01.

enter image description here

After I converted the NFA to the equivalent DFA.

it became
enter image description here

the issue is that the NFA accepts the string “101” but the DFA doesn’t.

Is my conversion wrong or is there something I am missing about the NFA to DFA conversion?

finite automata – NFA for words who start and end with different letters with $O(log(| Sigma |))$ states

The original question referred to DFA (and not NFAs). However, no DFA for $L$ with $O(k)$ states exists.

Consider $Sigma$ as a set of words (i.e., each word consists of a single character from $Sigma$).
Given any two distinct words $a,b in Sigma$, the word $a$ is a distinguishing extension for $a$ and $b$. I.e., $aa notin L$ but $ba in L$.

This shows that the number of equivalence classes of $L$ w.r.t. the equivalence relation “not having a distinguishing extension” is at least $|Sigma|$.
By the Myhill-Nerode theorem, any DFA for $L$ must have at least $|Sigma|$ states.


The idea to build a NFA with $O(k)$ states is as follows:
in addition to an initial state $s$, and to an accepting final state $t$ there are $2k$ states indexed with $1, dots, 2k$.

Assign a distinct integer $x_a$ from $0$ to $2^k-1$ to each character $a in Sigma$ and consider the binary string $b_a$ of length $2k$ obtained by concatenating the binary string of length $k$ representing $x_a$ in binary, with its complement.

For each character $a in Sigma$ let $S_a$ be the set of all states $i$ such that the $i$-th least significant bit in $b_a$ is $1$, and define $overline{S}_a = {1, dots, 2k} setminus S_a$.

For each $a in Sigma$, add the following transitions:

  • A transition from $s$ to each state $i in S_a$.
  • A transition from each state $i in {1, dots, 2k}$ to itself.
  • A transition from each state $i in overline{S}_a$ to $t$.

All unspecified transitions go to an additional rejecting state.

Given a word $sigma_1, sigma_2, dots, sigma_n$ with $sigma_1 neq sigma_n$, let $i$ be an index such that the $i$-th least significant bit of $b_{sigma_1}$ is $1$ while the $i$-th least significant bit of $b_{sigma_n}$ is $0$ (such an index always exists).
Then, $s to i to i to dots to i to t$ is an accepting path in the NFA.

Conversely, any accepting path is of the form $s to i to i to dots to i to t$ for some $i$. This implies that $i in S_{sigma_1} cap S_{sigma_n}$, i.e., $b_{sigma_1}$ and $b_{sigma_n}$ differ (at least) on the $i$-th least significant bit. This shows that $sigma_1 neq sigma_n$.

The number of states of the NFA is $2k+3$.

Give the Regular-Expression (NFA) with specific Separation Patterns

Question:
Given the RE (or NFA) for the set of all strings over $Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,ngeq 0$ b’s.

Attempt:
Followed the way we construct the set of strings such that $a$ occurs the odd number of times, I got the following solution:
$$b^*a(bb(bb)^* abb(bb)^*a)^*$$
But then I found the pattern $abbaa$ is not acceptable, as $a$ can appear multiple times consecutively. Is there any systematic way to solve the above problem?

nondeterminism – Constructing an NFA that is equivalent to a regular expression

I am a little stuck at attempting to give an NFA for the regular expression $0^+(10^+0)^∗$
, where the alphabet is ${0, 1}$. I have tried to construct multiple NFA’s state diagram and the closest I can come up with is enter image description here

However, I see that this NFA also accepts $0^+(10^+0)^∗0^*$. Is there any way I can alter this state diagram so that it only recognizes $0^+(10^+0)^∗$? I feel that I am missing something simple here…

Explaining NFA in words

I have an NFA, and the question I am asked is :

Let 𝑎 < 𝑏 < 𝑐. Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.

In simple English, my answer is

The NFA accepts strings over alphabet {a, b, c} such that the last symbol appears twice.

Which I know is correct, however my problem lies in the question where "a < b < c". How does this affect my NFA and is my answer still correct? My answer seems really short for 6 marks.enter image description here

finite automata – Constructing a NFA that accept complement of language L of another NFA

Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.

Is there a polynomial time way to do it? I don’t know, since the construction above can be exponential time in the number of states (because of the powerset construction).

Finite loop on a NFA

Some of this depends on what you mean by “tries.” But here is a reasonable first whack.

Suppose that the password is ab and you want to give a person two tries. Take q0 to be the initial state, take q2 to be the only accepting state, take q3 to mean “first try failed, initalize second try” (and it might light a light, warning the inputter that their first try failed). Also take q5 to be the (non-accepting) state meaning two-try failure.

Coming from q0 are two arrows, one to q1 labeled a and one to q3 labelled b. From q1 are two arrows, one to q2 labeled b and one to q3 labeled a. From q2 is a loop, labeled any.

You get the idea. From q3 are two arrows, one to q4 labeled a and one to q5 labeled b. From q4 come two arrows, one to q2 labeled b and one to q5 labeled a. From q5 is a loop, labeled any.

This is of course hopelessly naive from a security standpoint. But it gets across the basic idea.