The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes

If all state of DFA is final then it accpets $\sum$ (i.e) regular

true or false

asked in Theory of Computation by Boss (12.6k points) | 119 views

2 Answers

+1 vote

as in dfs there is always a move on any symbol at any state so it will accept .
answered by Active (2.7k points)
but what if it is a DFA accepting suppose (ab)* but max such that the number of a nd b's is 10

then how come it accepts sigma*
In case of (ab)* all states are not final state. In question they have mentioned if all states are final state.
okay then assume the dfa is accepting atmost 2 a's

in that case all states are final ststes right

but it isnt accepting sigma*
post dfa which you draw.
In case of atmost 2 a's you have to introduce a dead state which make sure if number of a's is grater than 2, then you wont get to final state or you get trapped, again dead state is not final state, in question they have mentioned "if all states of DFA is final states then .. "
got it :) @stblue
0 votes
yes it is true because in dfa we show transition for every symbol on each state .if we have a dfa which accepts all strings (0+1)* for a given input symbols {0,1,2} then for any transition with 2 as the input symbol will lead to a dead state / trap state.when we make all the states as accepting states we include dead state also otherwise it will not be (sigma)^(*).
answered by Loyal (5.9k points)

Related questions

0 votes
1 answer
asked Nov 3 in Theory of Computation by Na462 Loyal (7.4k points) | 44 views

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

44,240 questions
49,723 answers
65,839 users