Register

DFA

• edited by
1,407 views
0 0 votes
Give DFA's accepting the following languages over the alpha- bet (0,1):  *a) The set of all strings beginning with a 1 that, when interpreted as a binary integer, is a multiple of 5. For example, strings 101, 1010, and 1111 are in the language; 0, 100, and 111 are not.

1 Answer

Best answer
1 1 vote

Divisible By 5

String starting with 1

 

The set of all strings beginning with a 1 and is a multiple of 5

Finally use minimization algorithm to check if any state is redundant

(I've verified it on paper this cannot be minimized further, too lazy to do it here again :p)

• selected by
Voting & Accepting an answer helps improve the community
← Previous · Theory of compiler...Next → · #selfdoubt
← Previous in category · DFA constructionNext in category → · ISI2022 - MCS - PCB ...
Position:
Show:

Related questions

4 4 votes
3 3 answers
287
287 views
GO Classes asked Jul 6
287 views
GO Classes DPP | GATE CS | Theory of Computation | DFA Minimization
Consider the DFA over $\Sigma = \{a,b\}$ with states $q_0,q_1,q_2,q_3,q_4$. The start state is $q_0$, and the final states are $q_2$ and $q_4$. The transition function is...
4 4 votes
5 5 answers
272
272 views
GO Classes asked Jul 6
272 views
GO Classes DPP | GATE CS | Theory of Computation | DFA Modification
Consider the following finite state machine $A$Which modification makes it a DFA for $L = \{w \in \{a,b\}^* \mid w$ starts with $a$ and has exactly two $a$'s$\}$?Replace ...
5 5 votes
1 1 answer
164
164 views
GO Classes asked Jul 6
164 views
GO Classes DPP | GATE CS | Theory of Computation | String Tracing DFA
The following DFA accepts all those strings in which number of $1$'s and $0$'s areDivisible by $3$ and $2$ respectively. Odd and Even respectively. Even and Odd respectiv...
3 3 votes
2 2 answers
184
184 views
GO Classes asked Jul 6
184 views
GO Classes DPP | GATE CS | Theory of Computation | Equivalent DFA
Two finite state machines are said to be equivalent if they:Have the same number of edges Have the same number of states Recognize the same set of strings Have the same n...