Linked Questions
80 questions linked to/from How to convert finite automata to regular expressions?
2
votes
1
answer
29k
views
Regular expression for language with even number of 0's and 1's [duplicate]
Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of 0ドル$'s and an even number of 1ドル$'s?
If we only require an even number of 0ドル$'s, the language ...
0
votes
1
answer
28k
views
Converting NFA to regular expression [duplicate]
Here is the regular expression I made for it
This is my first answer, used the naive method aka don't know what am doin' method.
$$
\epsilon \cup a^* \cup (a^*b) \left((a| b^*a) | \left( (a|(b^*a))ba^...
3
votes
1
answer
2k
views
Complete explanation of state elimination methods [duplicate]
I'm so sorry if this question is too general, but I need to understand the general process of the "State elimination method".
In other words, what is the general idea, and what is the ...
1
vote
1
answer
1k
views
A regular expression for an automaton which accepts strings with no more than 3 consecutive zeros [duplicate]
This is the automaton I want to find the regular expression for:
As you see, states Q1 to Q4 are accepted and Q5 is a kind of trap. This automaton accepts strings that have no more than 3 consecutive ...
2
votes
2
answers
467
views
What's the regex corresponding to this DFA? [duplicate]
Here is a DFA from a research project. We created the DFA manually.
We are interested in which regex is this DFA corresponding to.
Certainly, there could be multiple regex corresponding to it; we ...
0
votes
1
answer
699
views
Can this DFA be converted to a regular expression? [duplicate]
I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?
-1
votes
1
answer
665
views
Converting DFA to regular expression [duplicate]
I have the following DFA. (Yellow stated are accepting states.) I want to eliminate states step by step to find the regular expression of it.
In my steps, I think there is a bug because I do not know ...
0
votes
1
answer
767
views
Program that generates a regular expression from an FA [duplicate]
Possible Duplicate:
How to convert finite automata to regular expressions?
Im curious if anyone knows if its possible to write a program to generate a regular expression given a finite automation. ...
user avatar
user3115
0
votes
0
answers
177
views
Proving a regular expression is correct [duplicate]
I'm working on homework for my formal languages and automata course. The text we are using is the first edition of Hopcroft and Ullman (1979).
Specifically, I'm unsure how to justify that my regular ...
-2
votes
1
answer
141
views
Regular Expression for the given DFA [duplicate]
Hi, what should be the regular expression for this language ? My guess was
r = (a
∗
a(a + b)
∗
(a + b) + (a
∗
b + c))(a + b
∗
)
∗
But the arrow from C to B is making it tough . If it was B to C ...
0
votes
0
answers
112
views
Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization [duplicate]
I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please ...
1
vote
1
answer
99
views
Defining if a language is regular [duplicate]
$L_4 = \{ w | w \text{ does not contain symbol a immediately followed by symbol b} \} $
where: $ \Sigma = \{ a, b, c \} $
So far I believe I have a defined regular grammar for this language, however ...
0
votes
1
answer
73
views
What language should the following DFA recognise? [duplicate]
My question is: what language should the following DFA recognise?
It seems that it should contain an odd number of substrings in the form 11*0. However, I am not sure whether there are any other ...
2
votes
0
answers
66
views
How to construct an NFA [duplicate]
I am trying to learn how to construct an NFA state diagram.
$$M = \{q0, q1, q2\}, \{a,b\}, \delta, q0 , \{q2\}$$
$δ(q0,a) = q0; \delta(q0,b) = {q0,q1}; \delta(q1,a)= {q0, q2}; \delta(q1,b) = {q1}; \...
0
votes
1
answer
63
views
How do you get a regex from this DFA? [duplicate]
I've been trying for hours. I'm teaching myself automata theory right now and I have this DFA:
And I'm trying to create a regex from it by removing q1 first and then q2. I already managed to remove q1 ...