The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+24 votes
2.2k views
The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______.
$$a^*b^*(ba)^*a^*$$
asked in Theory of Computation by Veteran (105k points)
edited by | 2.2k views
0
can anyone give nfa for this regular expression?

4 Answers

+58 votes
Best answer

$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

answered by Veteran (55.2k points)
edited by
0

Praveen Saini  how did u get this?

+2
0 length strings over {a,b} = $(a+b)^0= \epsilon$

1 length strings over {a,b} = $(a+b)^1=a,b$

2 length strings over {a,b} = $(a+b)^2= (a+b)(a+b)= aa,ab,ba,bb$.

so on
+1

 @Praveen Saini why r  u not finding the language derived from R = a*b*(ba)*a* and complement it! can this be an approach ?

0

yes that is same thing, you can find language of R, L(R), then complement, L'(R), then first element of L(R') will be bab.

0
Good Explanation

Thqq
0
@praveen Saini .i didn't get that approach compliment one .can u please elaborate!!!!!!!!!

although i understand the given approach.....help
0
Please draw once then explain m not getting how to solve this???
0
can u draw finite automata for the regular expression?
0

@suneetha @ Ankit @ Phalkey

In the DFA of the language (for given regular expression), shortest string that is NOT belong to the Language is,the shortest string that reach to a non-final state from the start state $q_0$.

$q_0\xrightarrow{\text{bab}}q_3$

$q_0\xrightarrow{\text{baab}}q_5$

I hope now it is clear that $bab$ is the answer

+9 votes

The big give away is the concatenation (ba)*  followed by a*

answered by Junior (853 points)
+7 votes
the shortest length is 3.

answer:- "bab"
answered by Boss (19.7k points)
+5 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.
answered by Active (1.5k points)
0
@Vishal please explain with Diagram ..
Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

42,491 questions
48,518 answers
154,890 comments
63,247 users