Question

Let N be an NFA with $\mathbf{k}$ states that recognizes some language $\mathbf{A}$.

a. Show that if $\mathbf{A}$is nonempty, $\mathbf{A}$contains some string of length at most k.

b. Show, by giving an example, that part (a) is not necessarily true if you replace both $\mathbf{A}$’s by$\mathbf{A}$ .

c. Show that If $\mathbf{A}$is nonempty, $\mathbf{A}$contains some string of length at most ${\mathbf{2}}^{\mathbf{k}}$.

d. Show that the bound given in part (c) is nearly tight; that is, for each $\mathbf{k}$, demonstrate an NFA recognizing a languagerole="math" localid="1660752484682" ${\mathbf{A}}_{\mathbf{k}}\mathbf{\text{'}}$ where role="math" localid="1660752479553" ${\mathbf{A}}_{\mathbf{k}}\mathbf{\text{'}}$is nonempty and where ${\mathbf{A}}_{\mathbf{k}}\mathbf{\text{'}}$’s shortest member strings are of length exponential in $\mathbf{k}$. Come as close to the bound in (c) as you can.

Short answer

1. $\mathrm{A}$is nonempty and $\mathrm{A}$contains some string of length at most $\mathrm{k}$is proved.
2. By replacing $\mathrm{A}$’s by$\mathrm{A}$ is not necessarily true.
3. If $\mathrm{A}$is nonempty, $\mathrm{A}$contains some string of length at most $2^{\mathrm{k}}$.
4. The given statement is proved below.

Step-by-step solution

Non deterministic finite automata.

Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata. In Non deterministic finite automata, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined.

Given statement in (a) is proved.

a)

If $\mathrm{A}$is nonempty, there is a path through $\mathrm{N}$ from a start state to an accepting state. By removing cycles, we may suppose the path has length at most $\mathrm{k}$. The word along the edges of this path is a word of length $\le \mathrm{k}$accepted by $\mathrm{N}$. Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata. In Non deterministic finite automata, for a particular input symbol, the machine can move to any combination of the states in the machine. In other words, the exact state to which the machine moves cannot be determined.

Hence, $\mathrm{A}$is nonempty,$\mathrm{A}$ contains some string of length at most$\mathrm{k}$ .

Replacement A ’s by  A.

b)

There are a couple of things about such a Non deterministic finite automata ${\mathrm{N}}_{\mathrm{n}}$ that must be true:

It has more than one state and it has at least one cycle. And here must be trying to construct automation for $\mathrm{\Sigma }=\left\{0\right\}$

Every time create a cycle either $\overline{\mathrm{A}}$ becomes empty or there are "holes" in that cycle (non-accept states) which require another cycle and the construction of the machine that the situation recurses.

Extending $\text{Σ}$ a set of natural numbers $\mathrm{X}$. For each $\mathrm{n}\in \mathrm{X}$, there is a Non deterministic finite automata ${\mathrm{N}}_{\mathrm{n}}$of $\mathrm{n}$ states which accepts all numbers which are not divisible by $\mathrm{n}$(its just a cycle with one non accepting state same as the start state). Let a new Non deterministic finite automata $N_n$be the union of the ${\mathrm{N}}_{\mathrm{n}}$ for $\mathrm{n}\in \mathrm{X}$with an additional start state (which is accepting), which has a single ϵϵ edge to each of the start states of the ${\mathrm{N}}_{\mathrm{n}}$. The natural numbers not accepted by ${\mathrm{N}}_{\mathrm{n}}$are precisely the nonzero multiples of $\mathrm{lcm}\left(\mathrm{X}\right)$, and ${\mathrm{N}}_{\mathrm{n}}$has $1+{\sum }_{\mathrm{n}\in {\mathrm{X}}^{\mathrm{n}}}$ states.

If  A is nonempty, A contains some string of length at most 2k

c)

Use the subset construction to find a deterministic finite automata$\mathrm{D}$ accepting $\mathrm{A}$.

If $\mathrm{A}$is nonempty, there is a path through $\mathrm{N}$ from a start state to an accepting state. By removing cycles, we may suppose the path has length at most $\mathrm{k}$. The word along the edges of this path is a word of length $\le \mathrm{k}$ accepted by $\mathrm{N}$. Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata.

Hence ,$\mathrm{A}$ is nonempty,$A$ contains some string of length at most$\mathrm{k}$ .

$\mathrm{D}$has less or equal to$2^{\mathrm{k}}$ vertices by construction. Let$\mathrm{D}$ ′ be the deterministic finite automata obtained from$\mathrm{D}$ by reversing the accepting states (a non accepting state is now accepting and vice versa).

Then $\mathrm{D}$′ accepts ${\mathrm{A}}^{\text{'}}$.

Apply the argument from the first part to find a word of length ≤ $2^{\mathrm{k}}$which $\mathrm{D}$’ accepts, or equivalently lies in ${\mathrm{A}}^{\text{'}}$.

Hence, If $\mathrm{A}$is nonempty, $\mathrm{A}$contains some string of length at most $2^k$is proved.

Given statement in (d) is proved.

d)

Let the alphabet consist of one letter 'one', and consider words as their corresponding natural numbers in unary.

Fix a set of natural numbers $\mathrm{X}$. For each $\mathrm{n}\in \mathrm{X}$, there is a Non deterministic finite automata ${\mathrm{N}}_{\mathrm{n}}$of $\mathrm{n}$states which accepts all numbers which are not divisible by $\mathrm{n}$(its just a cycle with one non accepting state same as the start state). Let a new Non deterministic finite automata ${\mathrm{N}}_{\mathrm{n}}$be the union of the role="math" localid="1660753637746" ${\mathrm{N}}_{\mathrm{n}}$for $\mathrm{n}\in \mathrm{X}$with an additional start state (which is accepting), which has a single ϵϵ edge to each of the start states of the${\mathrm{N}}_{\mathrm{n}}$ . The natural numbers not accepted by ${\mathrm{N}}_{\mathrm{n}}$are precisely the nonzero multiples of $\mathrm{lcm}\left(\mathrm{X}\right)$, and${\mathrm{N}}_{\mathrm{n}}$ has $1+{\sum }_{\mathrm{n}\in {\mathrm{X}}^{\mathrm{n}}}$ states. Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata.

for instance take$\mathrm{X}$ to be the primes less than $\mathrm{p}$ for some$\mathrm{p}$ to obtain one parameterized sequence of Non deterministic finite automata ${\mathrm{N}}_{\mathrm{n}}$ with the required property.

Indeed, arguing very coarsely, ${\mathrm{N}}_{\mathrm{n}}$has at most $\mathrm{p}$states but the first number not accepted is at least$2^{\mathrm{\pi }\left(\mathrm{p}\right)}\ge 2^{\mathrm{p}/\mathrm{logp}-1}$ for sufficiently large $\mathrm{p}$. Unfortunately this is only super polynomial in the number of states, and not quite exponential.