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

I got 3 states...

Given is 4 

asked in Theory of Computation by Veteran (17.1k points) | 72 views
I also got 3 states only..is the language aa(aaa)^* ?
same here

2 Answers

0 votes
This language can be further modified as

S-Saaa|a

Which will generate language a(aaa)*.

For which at least 4 states are required to draw the DFA.
answered by (73 points)
reshown by
What about string "aa" or "aaaaa"
0 votes
S -> Xa|Ya

S -> Zaa|Wa

S -> Saaa|Saa|E

as there is a possibility of coming aaa as the substring of the given language. So it will contain 4 states to achieve it.
answered by (35 points)


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

33,687 questions
40,230 answers
114,266 comments
38,783 users