Questions about regular expressions, a formalism to describe regular languages.
1
vote
1answer
41 views
Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?
I have an exam coming up and I need help with the following homework:
Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove ...
0
votes
1answer
46 views
Regular expression for odd binary numbers without leading zeros
I have to write a regular expression that accepts any odd binary number not preceded by a 0. the best I can come up with is $1(0\cup1)^*1$, but that doesn't match just 1. The best it matches is 11.
1
vote
2answers
101 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 ...
5
votes
3answers
99 views
Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?
Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of ...
3
votes
2answers
65 views
Does $c^*(b \cup (ac)^*)^*$ define all strings over $\{a,b,c\}$ that don't contain the substring $bc$
I'm reading my textbook and it claims that the regular expression $c^*(b \cup (ac)^*)^*$ defines the language $L$ over $\{a,b,c\}$ which consists of all strings that do not contain the substring $bc$. ...
5
votes
3answers
46 views
For regular languages A and B, determine whether B might match early in (A B)
I have two regular languages A and B, and I want to determine whether there is any pair of strings, a in A and b in B, such that (a b) is a prefix of a string in (A B) and the left-most ...
3
votes
3answers
55 views
How to find specificity of a regex match?
I'm thinking about a routing system. Imagine I have the two following regexes
pathpart1/pathpart2 => specific match that routes to controller1
.* => catch-all that routes to controller2
And I let ...
3
votes
1answer
49 views
Difference between pattern matching and pattern searching in terms of DFA/Regex
E.g.
Matching Problem The DFA of regex good is like a chain.
...
3
votes
0answers
40 views
Distinguishing probabilistic, deterministic, and fuzzy matching methods
I have two datasets that I am trying to match to one another. One dataset's contents is a subset of the other, but contains typographical errors of varying types and magnitude.
I am applying the ...
2
votes
1answer
71 views
DFA to regular expression conversion
I was looking at the question How to convert finite automata to regular expressions? to convert DFA to regex.
The question, I was trying to solve is:
I have got the following equations:
$Q_0=aQ_0 ...
2
votes
1answer
87 views
Finding simpler equivalent regular expressions
I'm doing an exercise from my book that says:
Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. Find a simpler equivalent regular expression:
a. $r(r^*r + r^*) + ...
4
votes
2answers
103 views
String of minimum length in $\{a, b\}^*$ not in a regular expression
I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression.
a. $b^*(ab)^*a^*$
My answer: ...
0
votes
0answers
74 views
Regular languages - models of computation [duplicate]
As far as a I understand, a regular language is a set of words that can be run in a DFA.
$L_1 = \{ x\#y \mid x,y \in \{0,1\}^* \ \text{and} \ |x| = |y| \}$
$L_2 = \{ xy \mid x,y \in \{0,1\}^* \ ...
1
vote
2answers
71 views
CFG with regular expression terminals on RHS
Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G_1$:
$\begin{align*}
S & \rightarrow (a ...
3
votes
1answer
80 views
Simplifying regular expressions
This is the homework question:
$ \{w \in \{a, b, c\}^* : \text{(no symbol occurs twice in succession in w)}\} $
This is my answer:
$$\{((abc)^*| (acb)^*| (ab)^* | (ac)^*)^* | (bac)^* | ...
