non-deterministic automaton

[eliz]

Hi, I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet {a,b,c} that accept all and only those strings that contain exactly three a's, three b's, or three c's, not necessarily consecutively .for example; strings l.ike {aaa, abaab, abbcccccccccccbaaa,cbccbbbbbbb,..} is accepted.

Thanks all

 

[stapel]

Hi, I am a linguistics and I start to read some books about Nlp.

I will guess that "Nlp" means "NLP", or "Neuro-Linguistic Programming". (Skeptical outline here.)

I have to design a non-deterministic automaton and regular expression over the alphabet {a,b,c} that accept all and only those strings that contain exactly three a's, three b's, or three c's, not necessarily consecutively. For example, strings like {aaa, abaab, abbcccccccccccbaaa,cbccbbbbbbb,...} is accepted.

"Strings" is plural; a set (as formatted above) is singular. Are you saying that you are supposed to create strings (or maybe count the possible number of strings); or that you're supposed to create a set of strings (or maybe find the cardinality of the set of strings), which would explain your use of the singular "is"?

When you reply, please include the full and exact text of the original exercise, the complete instructions, and a clear listing of your thoughts and efforts so far. Thank you!

 

[eliz]

...please include the full and exact text of the original exercise, the complete instructions, and a clear listing of your thoughts and efforts so far.

The exercise:

Design a non-deterministic automaton and regular expression over the alphabet {a, b, c} that accept all and only those strings that contain exactly three a's, three b's, or three c's, not necessarily consecutively. Strings in this language include:{aaa, abaab, abbcccccccccccbaaa,cbccbbbbbbb,...} . Also, design a regular expression for this language.

As a regular expression I think it would be like [bc]*a[bc]*a[bc]*a[bc]* but I'm not sure.

For an NDA, it would be like :

 

[Ishuda]

Hi, I am a linguistics and I start to read some books about Nlp. I have to design a non-deterministic automaton and regular expression over the alphabet {a,b,c} that accept all and only those strings that contain exactly three a's, three b's, or three c's, not necessarily consecutively .for example; strings l.ike {aaa, abaab, abbcccccccccccbaaa,cbccbbbbbbb,..} is accepted.

Thanks all

Is this what you mean?
Let F be end of string fail [there are not exactly 3 a's nor 3 b's, nor 3'c]. Let S be success [there are exactly 3 a's or 3 b's, or 3'c]. Let R be read a character. So

[State 0 a]
[FONT=courier new]R---b or c-------->R---->a---out to [State 1 a]
| \               |^ \
|   \             | \ \------->F
a     \           |  \  
|      \F        b or c   
|
out to [State 1 a]

[/FONT]
[FONT=courier new][State 1 a][/FONT]
[FONT=courier new]R---b or c-------->R---->a---out to [State 2 a]
| \               |^ \
|   \             | \ \------->F
a     \           |  \  
|      \F        b or c   
|
out to [2 a]

[State 2 a]
...[/FONT]

and continue with the last two sets for three a's with appropriate changes. Continue with build for b's and c's. If you can't reinitialize the string then you will have to write the string as you read it for the b and c set.

 

[eliz]

Is this what you mean?
Let F be end of string fail [there are not exactly 3 a's nor 3 b's, nor 3'c]. Let S be success [there are exactly 3 a's or 3 b's, or 3'c]. Let R be read a character. So

[State 0 a]
[FONT=courier new]R---b or c-------->R---->a---out to [State 1 a]
| \               |^ \
|   \             | \ \------->F
a     \           |  \  
|      \F        b or c   
|
out to [State 1 a]

[/FONT]
[FONT=courier new][State 1 a][/FONT]
[FONT=courier new]R---b or c-------->R---->a---out to [State 2 a]
| \               |^ \
|   \             | \ \------->F
a     \           |  \  
|      \F        b or c   
|
out to [2 a]

[State 2 a]
...[/FONT]

and continue with the last two sets for three a's with appropriate changes. Continue with build for b's and c's. If you can't reinitialize the string then you will have to write the string as you read it for the b and c set.

what do you think about my answer?