Hello 4chan, I'm new posting here and I think some of you could help me.
Actually preparing some final from the semester related to Regular Expresions, Automats, Turing Machines and so on, and I find one regular expresion that I find myself unable to think.
With the alphabet (a,b,c) I would like to form all the strings possibles that doesn't contain the substring "bca". I've been stucked in this one for like 2 days, but I just can't get it. Even mailed my teacher but she doesn't seem to answer me :/
Thanks to all.
>>146023
Sounds like an infinite cycle to me.
>>146366
Well what do you mean with infinite cycle?
>>146023
What's the actual point of the exercise?
This FSA can recognise it, which proves it's regular, and that it's possible to construct a regex from the FSA programmatically.
>>146540
The point is that for example in the exam they could ask me to construct that regexpr. and I want to prepare this and understand regexprs that doesn't allow substring of 3 characters with (a,b,c) (because always they ask that or strings formed by 1 or 0).
I think i control the aspect of constructing Automats, DFAs and NFAs are under control but I can't construct the regexpr from them. And by the way what do you mean exactly with FSA (I only know DFA and NFA) is something like Finite Stack Automat? I'm from spain so we call all this things different and I dont want to mess you with the translations.
Thanks again ^-^'
>>146576
FSA (Finite State Automaton/Automata) is just a catchall term that includes both DFA and NFA. Because DFA are complete on NFA*, there's often no reason to draw the distinction.
* https://en.wikipedia.org/wiki/Powerset_construction
>>146729
Oh yes, now I get that, ok. But I already know how to convert NFA into DFA, but thanks ^^.
My problem is to try to find the regexpr that can express that regular language, kind of for example if I say, all the strings that allow the substring "101" with the characters of the alphabet {1,0} it should be something like this:
(1 | 0 )* 101 (1 | 0)* Which means all the 0s and 1s that I could ever want followed by the substring 101 and then ending by all the 0s and 1s that i could ever want.
Or for example if I say, the regrexp that represent the language that can form all the strings with the alphabet {a,b,c} that doesn't allow the substring "ab" it would also be something like:
(b | c)* ( c | a | c+b* )* Which means all the b or c that I could want followed by all the c or a or all the C, but at least one, that i could want followed by all the b that i could want, all of this repeated al the times that i could want.
And this is what i want to findfor the excersice, the regrexp that represent that language ^^ Thanks