#peter_linz

Question

what is the length of the shortest string not in the language(over 0,1) for regular expression 1*(0+10)*1* ??

Comments

$\text{0110}$

Either figure out just from regex or $\epsilon - NFA \rightarrow NFA \rightarrow DFA $

Answer 1

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

The language into consideration is 1*(0+01)*1*.

this language will accept all strings of length 0,1,2 and 3. Coming to length 4 we will see that the strings in which we have a zero followed by >=2 ones cant have a zero after it for eg:0110. This string is not contained in this grammar.

Comments

is this the only possible approach to solve this question??

---

see what pattern this particular grammar is making and then check what it accepts and what not.. like in this case we see after a zero followed by 2 1,s cant have more 0's following it so.. we see that this is the minimum case ..

---

vaibhav singh 3 or else you can create a DFA and check in how many steps you are reaching trap state or staying at non-final state