Linked Questions

1
vote
1answer
19k 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
1answer
15k 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^...
-1
votes
1answer
551 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 ...
2
votes
2answers
324 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
1answer
614 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....
1
vote
1answer
521 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 ...
0
votes
0answers
107 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
1answer
98 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 ...
1
vote
1answer
76 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
1answer
57 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 ...
0
votes
1answer
39 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?
2
votes
0answers
51 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
0answers
35 views

What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
1answer
34 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 ...
0
votes
0answers
33 views

Find language (and/or regular expression for automaton) [duplicate]

How do I go about finding a language recognized by the following automaton? And is it possible to find a corresponding regular expression? I've read some posts about the same issue here on CS.SE but ...

15 30 50 per page