Linked Questions
12 questions linked to/from Check whether a regular expression is correct
0
votes
0
answers
720
views
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 ...
0
votes
0
answers
104
views
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 $...
54
votes
9
answers
130k
views
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 ...
- 889
13
votes
5
answers
5k
views
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. ...
- 257
14
votes
2
answers
10k
views
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 ...
10
votes
3
answers
3k
views
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 ...
6
votes
2
answers
14k
views
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.♦
- 164k
10
votes
1
answer
2k
views
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.
- 675
2
votes
2
answers
10k
views
Convert regular expression to DFA
How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
messivp
0
votes
1
answer
1k
views
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"...
- 255
1
vote
2
answers
1k
views
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 ...
- 11
0
votes
0
answers
174
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 ...
- 9