edited by
13,544 views
54 votes
54 votes
The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______.
$$a^*b^*(ba)^*a^*$$
edited by

5 Answers

Best answer
108 votes
108 votes

$R = a^*b^*(ba)^*a^*$

for finding shortest string that is not in language it is better to look strings of length $0$, then of length $1$ and so on 

$\text{length}0 \{ \epsilon \}$  is in $L$

$\text{length}1 \{a, b\}$      all belong to $L$

$\text{length}2 \{aa, ab, ba, bb\}$      all belong to $L$

$\text{length}3 \{aaa, aab, aba, abb, baa, bab, bba, bbb\}$  bab does not belong to L

edited by
6 votes
6 votes
To be completely sure of the right answer, construct an ɛ-NFA for the given language, convert it into an equivalent DFA and then complement it. The answer comes out to be bab.
Answer:

Related questions

22 votes
22 votes
5 answers
1
go_editor asked Sep 28, 2014
13,490 views
A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks nev...
31 votes
31 votes
5 answers
2
go_editor asked Sep 28, 2014
10,810 views
If $\int \limits_0^{2 \pi} |x \: \sin x| dx=k\pi$, then the value of $k$ is equal to ______.