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

I got 3 states...

Given is 4 

asked in Theory of Computation by Boss (18.2k points) | 108 views
+1
I also got 3 states only..is the language aa(aaa)^* ?
0
same here
0

finally we got S->aa/Saaa

means L=aa+aaa(aa)+

please correct me if i am wrong 

0

Gurdeep Saini  L=aa+aaa(aa)

by this language ( 7 times a) also accepted according to u but i am not able to find any string of 7 length

0

thanks @deepanshu 

now check again

L=(aaa)*(aa)

+1

Gurdeep Saini hmm now i think we can accept sequences 2,5,8,11 so from my view it is correct

: )

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 (71 points)
reshown by
0
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 (39 points)

Related questions

0 votes
0 answers
3


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

46,786 questions
51,234 answers
176,575 comments
66,585 users