Example NFAs University Questions

Construction of a minimal NFA accepting a set of strings over {a, b} in which each string of the language ends with 'ab'.

L = {w ∈ {a, b} : w starts with a}

What happens if a ’b’ is seen in state q0?The machine “crashes”, and does not accept the string

L = {w ∈ {a, b} : w contains the substring aa}

Create an NFA for:
All strings over {a, b} that start with a and end with b

All strings over {0, 1} that contian 0110 or 1001

ε transition consumes no input NFA (with ε transitions) for (ab)*(aab)*

Create an NFA (with ε-transitions) for: All strings over {a, b, c} that are missing at least one letter. For example, aabba, cbbc, ccacc ∈ L, while abbc ∉ L

Identify the language accepted by this machine

Give an NFA for the language L = All strings over {0,1} that contain two pairs of adjacent 0’s separated by an even number of symbols. So,0100110011, 01100101100101, and 01001000 are in the language, but 0100100, 1011001,and 0111011 are not in the language.

Create an NFA for the language L = All strings over {a,b} that have an a as one of the last 3 charaters in the string. So, a, baab, bbbab, aabbaaabb ∈ L, but bb, baabbb, bbabbbbb ∉ L

Design an NFA with ∑ = {0, 1} for all binary strings where the second last bit is 1.

The language generated by this example will include all strings in which the second-last bit is 1.

L= {10, 010, 000010, 11, 101011……..}

Please design an NFA with input alphabet ∑ = {0, 1} that accepts all the strings that end with 01.

Solution

The language generated by this example will include all strings that end with 01.

L= {01, 0101, 0000101, 101, 101001……..}

Construct an NFA with ∑ = {0, 1} in which each string must contain “double ‘1’ is followed by single ‘0’.
The language generated by this example will include all strings that must contain “double ‘1’ is followed by single ‘0’.

L= {110, 0110, 1110, 10100110……..}

Draw an NFA with ∑ = {0, 1} such that the third symbol from the right is “1”.
The language generated by this example will include all strings where the third symbol from the right is “1”.
L= {100, 111, 101, 110, 0100, 1100, 00100, 100101……..}

Construct an NFA with ∑ = {0, 1}, where each string must contain either “01” or “10”.

The language generated by this example will include each string must contain either “01” or “10”.

L= {01, 10, 001, 110, 1110, 0001………..}

Construct an NFA with ∑ = {0, 1} that accepts all strings that begin with 1 and end with 0.

The language generated by this example will include all strings that begin with 1 and end with 0.

L= {10, 110, 100, 1100, 1110, 1000 ……

Construct an NFA with ∑ = {0, 1} for the language  L = {0m1n | m ≥0 and n≥1 }

The language-generated strings will be like as

When m=0  and n=1, the string will be 1 because 0011=1.When m=1 and n=2, then the string will be 1 because 0112=011.When m=2 and n=3, then the string will be 1 because 0213=00111.By choosing a random value, i.e., When m=3, n=2, the string will be 1 because 0312=00011.And so on.

Construct an NFA with ∑ = {0, 1} for the language L = {(01)n | n≥1 }.

Solution

The language-generated strings will be like as

When n=1, the string will be 01 because (01)1=01. When n=2, the string will be 0101 because (01)2=0101. By choosing a random value, i.e., n=5, then  (01)5=0101010101. And so on.