Register

practics paper

380 views
1 votes
1 votes
consider following input sequence 01010101............

A) what will be regular expression to accept all prefixes of the given sequence__

1. 0(10)*

2. 0(01)*

3. 0(10)*+(01)*

4. 0*+(101)*

B) how many minimum number of state are required in a DFA for accepting the correct regular expression?

a.3

b.2

c.4

d.5
User Avatar

1 Answer

Best answer
1 votes
1 votes

A) answer must be 3.

1. 0(10)*  //Cannot accept the prefix 01

2. 0(01)*  // accpets the wrong prefix 001 and cannot accpet 010

3. 0(10)*+(01)*      

4. 0*+(101)* // Cannot accept the prefix 01

So option 3 must be the answer

B. We need 4 states to represent this sequence

• selected by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
Hira Thakur asked Aug 29, 2016
359 views
practics paper
which of following regular expression generate the set of all string not cantaing "baa" as a substring over the input alphbet{a,b} is___ 1 a*(b*a*) 2 a*b*ab 3 a*baba* 4 a*(ba+b)*
which of following regular expression generate the set of all string not cantaing "baa" as a substring over the input alphbet{a,b} is___1 a*(b*a*)2 a*b*ab3 a*baba*4 a*(ba...
User Avatar
4 votes
4 votes
0 answers
2
Hira Thakur asked Aug 29, 2016
817 views
practics paper
if M1 machine recognizing L1 with n state the M recognizing L1* constructed using thomson construction will have minimum number of states 1. n 2 n+1 3. n+2 4. n-1
if M1 machine recognizing L1 with n state the M recognizing L1* constructed using thomson construction will have minimum number of states1. n2 n+13. n+24. n-1
User Avatar
1 votes
1 votes
1 answer
3
Hira Thakur asked Aug 29, 2016
193 views
practics paper
the left liner grammer given below genrates H→Ha/a S→Hb 1.(a+b)^+ 2.aa*b 3 a*b 4 none
the left liner grammer given below genratesH→Ha/aS→Hb1.(a+b)^+2.aa*b3 a*b4 none
User Avatar
1 votes
1 votes
0 answers
4
Hira Thakur asked Aug 29, 2016
135 views
practics paper
the number of state in MDF of the language {L(10*10*1) U L(01*01*0)} is_______???
the number of state in MDF of the language {L(10*10*1) U L(01*01*0)} is_______???
User Avatar
Link Copied!