Linked Questions

0 votes
0 answers

Strings that do not contain 11 as a substring [duplicate]

Today I had a couple of formal language lectures. The Instructor wrote a regular expression for the alphabet $\{0,1\}$ which does not include any string which includes "11" as a substring. She wrote ...
no one ever's user avatar
0 votes
0 answers

Deciding the language of DFAs accepting $(101)^*$ [duplicate]

I want to prove that $L = \{\langle T\rangle\mid T \text{ is a DFA and $L(T)$=$(101)^*$}\}$ is decidable. I have the following idea in mind: I design a TM $M$ such that, first of all, $M$ converts $...
user913923219's user avatar
53 votes
9 answers

How to prove a language is regular?

There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular? For instance, if I am given that $L$ is regular, how can I prove that ...
corium's user avatar
  • 879
13 votes
5 answers

Proving Equivalence of Two Regular Expressions

Consider the regular expressions $(1+01)^*(0+\epsilon)$ $(1^*011^*)^*(0+\epsilon) + 1^*(0+\epsilon)$, where $\epsilon$ is the empty string. I need to determine if these expressions are equivalent. ...
Keio203's user avatar
  • 257
14 votes
2 answers

Algorithm to determine whether two regexes are equivalent

Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings? More generally, can we compute the size of the intersection of the ...
MathematicalOrchid's user avatar
10 votes
3 answers

How do I verify that a DFA is equivalent to a NFA?

I'm learning how to convert NFAs to DFAs and I want to make sure I'm doing it right. Obviously, going back in the other direction isn't a thing. Does anyone know of an algorithm to check that a DFA is ...
IAmOnStackExchange's user avatar
5 votes
2 answers

How do I find a regular expression for a particular language?

I have a language, and I want to find a regular expression for the language. How do I do that? Is there a step-by-step, systematic procedure for that? Pretend I am just learning this topic; what ...
D.W.'s user avatar
  • 156k
10 votes
1 answer

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
Duncan's user avatar
  • 665
2 votes
2 answers

Convert regular expression to DFA

How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
user avatar
0 votes
1 answer

Proving following regular expressions equal to one another?

How would I go about proving the following two regular expressions are equal to one another: ( a + b )* a ( a + b )* b( a + b )* = (a + b)* ab(a + b)* I can "see"...
Jenna Maiz's user avatar
1 vote
2 answers

Constructing a NFA from a regular expression

I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...
abeer00's user avatar
  • 11
0 votes
0 answers

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 ...
0culus's user avatar
  • 9