The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
127 views
Construct the Minimum FA that accepts all the string of 0's and 1's where

A)Every String start and end with Zero.

B)Every string Start and end with Same Symbol.
asked in Theory of Computation by (59 points) | 127 views
0
You can do it by construction the regular expression for the FA.

For the first, it will be: 0(0+1)*0 + 0

For the second, it will be: 0(0+1)*0 + 1(1+0)*1 + 0 + 1
0
Can you please give the State Diagram
0
What have you tried? If you show where you are stuck, maybe other people can help you.

1 Answer

0 votes
  • Starting and ending with symble 0

Starting and endin with same symble

 

 

answered by Boss (23.3k points)
edited by
0
This is correct, but don't you think OP should at least show what he is attempted before he's given an answer?
This way, he'll blindly copy your answer and may not learn to solve a similar question of a different type.
+1
why do you not include epsilon?

Epsilon is also start and end with the same symbol
0
Updating now
+1
epsilon is not a symbol of alphabet, then how you include it?

please clarify me.
+1
@shaikmasthan

epsilon is one of the string which belongs to above language .

R.E should give every possible string in language...so epsilon need to be included.!
+1
Yes shubham is right
+1
@shubham, if it is in the language then it should be included in regular expression...

my doubt is is epsilon should be in language?

means

epsilon doesn't start and end with any symbol of input alphabet
0
L={εεε,0,1,00,11,01,10,000.......}

In the above language, we have to select those languages which start and end with the same symbol.

B) L'={ε,0,1,00,11,010,101,........}

we can write ε=εεε

hope you understand now.
0
@ shaik masthan you are correct i misread the qsn..thanks for correcting epsilon should not be included..!
0
@suraj patel, then cbc also in language. it is also starting and ending with same symbol.
0
No, because the acceptable string will only the forms of 0's and 1's not a,b,c.
0
how you recognizing that a,b,c is not in input alphabet, as the same way epsilon also not belongs to the language.
0
ok, let's think about some regular expression rules.

1)  0ε=0=ε0

suppose if we replace ε by a or b or c

0a=a or a=a0 ?
0
can you perform 1st part using concatenation.

please show me.
0

@suraj patel, my intension is not querying with you...

if you are saying ∈ also in Language then, starting and ending with 1 also should be in language

due to 1 = ∈ . 1 . ∈

11 = ∈ . 11 . ∈

if you are not getting comment one more time....

 



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

39,751 questions
46,767 answers
140,662 comments
58,537 users