266 views

1 Answer

2 votes
2 votes

The NFA for the given regular expression 1*(0+10)*1* is given below

To find the shortest string which is not accepted by the above NFA we have to find those states which do not have transition for some symbol.

Note that after reaching q3 there is no transition for 1. So,if we have the string 011 then we reach the state q2. And from q2 there is no transition for 0. So, the string 0110 is not accepted.

The shortest string which is not in the language is of length 4.

It is the string 0110.

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
2 answers
3
jugnu1337 asked Sep 3, 2023
330 views
FIND the no of 2 state dfa with the designated initial state possible over {a,b,c} which accept empty language is equal to