Questions about regular expressions, a formalism to describe regular languages.
1
vote
1answer
58 views
Converting an NFA to regex using GNFA algorithm?
So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.
Given the following NFA:
Using the GNFA algorithm get the regular expression.
I ...
1
vote
4answers
94 views
Designing a regular expression for the set of all binary that contain strings without a particular sub string (i.e. $110$)
I'm still a newb at designing regular expressions without particular sub strings
for the case of a regular expression without sub string $110$ I Was thinking of: ...
1
vote
1answer
42 views
Is the language $a^{3}b^{+}$ the same as $\{a^{3}b^{n}, n \geq 1\}$ ? and what is the result of pumping this?
The regular expression $a^{3}b^{+}$ is indeed regular because we can define an automata $M$. But I see that $\mathcal{L} = \{a^{3}b^{n}, n \geq 1\}$ may generate the same strings, but using the ...
1
vote
1answer
51 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
55 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
108 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
120 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
66 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
48 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
56 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
45 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
113 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
89 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
107 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
75 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
82 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)^* | ...
3
votes
3answers
133 views
Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$
I have to make a regular expression from the following laguage:
{$a^kb^mc^n : $ where k + m + n is odd}
Is is possible for the sum of three numbers to be odd (other than three consecutive odd ...
3
votes
2answers
114 views
Distributivity of $\omega$-regular expressions
How can I prove that
$\qquad (E_1 + E_2).F^\omega$
is equivalent to
$\qquad {E_1.(F^\omega)+E_2.(F^\omega)}$
where
both expressions are omega regular expressions, and
$E_1$, $E_2$ and $F$ ...
2
votes
2answers
65 views
Regular expression for binary words with few zeros
What is the regular expression for the set of binary strings with the property that
every $0$ is followed by exactly $m$ times $1$ and
every $0$ is preceded by at least $n$ times $1$?
$m$ and ...
0
votes
1answer
67 views
What is meant by “give pattern of a regular expression”
I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. ...
1
vote
2answers
162 views
Is there a name/interest for regular languages that have a non-ambiguous ending?
The basic idea is to have one or more symbol that clearly indicate the end. For example:
Non-ambiguous:
$ab^*c$
$(a|b)c$
$ab^+c$
$ab?c$
$a(b|c)$
$c(ab)^*ccc$
$acc^*d$
...
0
votes
2answers
288 views
Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?
4
votes
2answers
208 views
Is this language regular or not?
$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$.
If it is regular, I haven't found its regular expression or any closure property to prove it.
If not, it seems ...
0
votes
1answer
97 views
Formal Languages - Expressive power of Formalisms
I need help with the following question:
Order the following formalisms according to their expressive power:
placing A before B means that any language definable by A is definable
by B. Also state ...
2
votes
1answer
30 views
I need to present a regular expression for the following languages:
1.
L2 = E{0,1)
All the words in L2 with equal number of 0's and 1's and every prex of w has at most two more of either
0's or 1's.
2.
All words that does not contain “bbb” as substring.
i think ...
1
vote
1answer
113 views
Does $(a \mid b)^*$ match $a^n$ and $b^n$?
I am getting confused by the regular expression $(a\mid b)^*$ as it for sure matches $aab$ and $ab$.
Does $(a\mid b)^*$ also match strings like $aa$, $aaaa$, $bb$ or $bbb$, that is those that use ...
2
votes
2answers
317 views
Simplification of regular expression and conversion into finite automata
This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. ...
3
votes
2answers
84 views
Language member explanation
Given the following formal language $L$:
$$ L=\{ww \mid w\in\{a,b\}^*\}$$
Why is $a$ not a member of this language?
So what is $\{a,b\}^*$ exactly? I thought it means $(a+b)^*$?
1
vote
1answer
94 views
Which of the following regular expressions generate(s) no string with two consecutive 1’s?
This is a GRE practice question.
Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)
I. (1 + ε)(01 + 0)*
II. ...
0
votes
1answer
64 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 ...
6
votes
1answer
167 views
Which languages do Perl-compatible regular expressions recognize?
As the title says, I spent a couple of hours last weekend trying to wrap up my mind about the class of languages matched by Perl-compatible regular expressions, excluding any matching operator that ...
7
votes
1answer
297 views
Is $(a^nb^m)^r$ regular?
I took my theory of computation exams a few weeks ago, and this was one of the questions:
Assume language $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$
Is L regular? If yes provide a regular expression ...
2
votes
1answer
146 views
Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$
Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.
4
votes
0answers
102 views
How to disambiguate symbolic regular expressions
What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
0
votes
1answer
142 views
Does this regular expression equal this automata?
I just came across an exercise which is to find a regular expression for the following automata, such that the regular expression and the automata generate the same language.
One solution presents ...
9
votes
2answers
409 views
Are regular expressions $LR(k)$?
If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
6
votes
1answer
95 views
regular expression given the language
The language is:
$$
L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \}
$$
My attempt at an answer:
$$
(a \cup b)^{3k}
$$
This will work if the a OR b can change for each instance in the string that is ...
1
vote
1answer
110 views
A regular expression for a given formal language
I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
5
votes
2answers
250 views
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata?
I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively ...
-1
votes
1answer
119 views
construct regular expression
I need help with the following exercise:
Construct an $\varepsilon$-NFA for the following regular expression $(a|\varepsilon)(ba)^*(c^*a|bc)^*$.
i already tried this exercise with nerode but i didnt ...
12
votes
4answers
5k views
How to convert finite automata to regular expressions?
Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms. The other direction seems to be more tedious, though, and sometimes the resulting ...
9
votes
2answers
342 views
Does the language of Regular Expressions need a push down automata to parse it?
I want to convert a user entered regular expression into an NFA so that I can then run the NFA against a string for matching purposes. What is the minimum machine that can be used to parse regular ...
-2
votes
2answers
392 views
Regular expression for all strings with at least two 0s over alphabet {0,1}
My answer : (0+1)* 0 (0+1)* 0 (0+1)*
Why is this incorrect? Can somebody explain to me what the correct answer is and why?
15
votes
1answer
186 views
“Dense” regular expressions generate $\Sigma^*$?
Here's a conjecture for regular expressions:
For regular expression $R$, let the length $|R|$ be the number of symbols in it,
ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup ...
3
votes
2answers
81 views
Regular Expression for the language that requires one symbol to occur at least once
I am trying to figure out the simplest way to do this using a regular expression.
Three symbols a, b, c.
The sequence length is unlimited, i.e. *.
The symbol a must be somewhere in the sequence at ...
9
votes
3answers
525 views
How to convert an NFA with overlapping cycles into a regular expression?
If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as ...
