Questions about regular expressions, a formalism to describe regular languages.

learn more… | top users | synonyms (2)

3
votes
1answer
37 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in ...
4
votes
1answer
51 views

How are REGEXP implemented in programming languages?

Is there a good general paper about the interpretation or compilation of REGEXP in programming languages for pattern matching, with or without variables? I am not looking for a quick explanation about ...
0
votes
2answers
64 views

Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this: ...
3
votes
1answer
107 views

Regular expression to show that all strings contain each symbol atleast once

I'm studying for my exam and I came across the following exam question from last year, the only way I know how to solve this is build a regex that accounts for all six different series of letters so ...
0
votes
2answers
52 views

find a regular expression and FA that each define $L_1 \cap L_2$

I am trying to find a regular expression and finite automaton that each define $L_1 \cap L_2$, where $L_1 = (ab^*)^*$ and $L_2 = ...
0
votes
1answer
51 views

Why $R\circ\emptyset$ is not always equal to $\emptyset$

I was going through the text Introduction to Theory of Computation by Michael Sipser. It is written that $R\circ\emptyset$ may not equal to $R$. I thought $R\circ\emptyset=\emptyset$ always. $R$ is ...
0
votes
1answer
33 views

About trap states when converting DFA to regular expression

If we were to have a trap state in a DFA and we are converting it to a regular expression, how exactly would I incorporate that into the regex? Let's say our language only accepts a*, and my DFA has a ...
0
votes
1answer
66 views

how did they get this answer for the words that don't have bba and abb?

I am looking at the answer in solution manual which asked , all the words that don't have both substring bba and abb. and the answer was a*(baa*)*b+b*(a*ab)*a* ...
5
votes
2answers
67 views

Context-free language and regular expressions

I have the following context-free language: S -> ASa | b A -> aA | a I don't understand why this is not regular. I first said that it's generated by the ...
0
votes
0answers
68 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 ...
1
vote
3answers
44 views

Precedence in regular expressions

I'm having trouble finding the language represented by the following: (AA|BB)* Should the expression be read as... ( A (A|B) B ) * or... ( (AA) | (BB) )* If that isn't clear, should this produce ...
4
votes
2answers
796 views

Difference between 1* + 0* and (1 + 0)*

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?
14
votes
1answer
284 views

Is regex golf NP-Complete?

As seen in this recent XKCD strip and this recent blog post from Peter Norvig (and a Slashdot story featuring the latter), "regex golf" (which might better be called the regular expression separation ...
0
votes
2answers
81 views

Why does a regular expression only accept all my required strings when the concatenation is the first of the OR operations?

I am having a bit of difficulty understanding the order of precedence in boolean logic for the OR operation. Take this example: Assume the following regular expression: ...
1
vote
1answer
216 views

Redundant States During Removal of Null-Moves (Regular Expression to DFA)

I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask. Coming to the question, my old coursebook ...
1
vote
1answer
142 views

Regex for the language over $\{a,b,c\}$ that contain at least two $a$'s but no two consecutive $b$'s

Like the title says, we have the alphabet $\Sigma = \{a,b,c\}$ and the question is asking for the regular expression of the language $L$ that has the property that all strings in $L$ have at least two ...
1
vote
0answers
19 views

Can regular expression captures be matched by a CFG being simulated by an $LR(k)$ parser?

I have seen this question: Are regular expressions $LR(k)$? and my question is slightly related. Suppose I have a regular expression: RE=(a*a*)?(a*a*) and I convert it to a grammar: G ::= A B A ::= ...
0
votes
3answers
393 views

NFA or DFA for strings the contain exactly twice substring ab?

Given the language with alphabet: $\{a, b, c\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody ...
1
vote
1answer
53 views

Regular expression for the language where every a is surrounded by b's

I had a question on an assignment where we were supposed to write a regular expression for a language where every $a$ in $w$ is immediately preceded and followed by a $b$. My answer was $\epsilon + (b ...
0
votes
1answer
82 views

A little help with regular expressions [duplicate]

I am trying to create a regular expression that will generate the following language under the {a,b,c} alphabet: all words that do not contain the substring "bbc" I am having a really hard time ...
1
vote
1answer
69 views

What can be defined as a Regular Set

I'm currently studying compilers and am having some issues with understanding regular sets. For example, lets say I had a set of binary strings, (0, 1). Would all integers that are even and positive ...
1
vote
1answer
45 views

Which grammar is this?

Having the grammar G = (V,P,S) with variable V = {S,A} over the alphabet {a,b} with the ...
3
votes
1answer
75 views

exact matching between two strings - linear edit distance?

This is the problem, given a string with characters from: a-z, ., *, and another string with ...
2
votes
1answer
56 views

Regular Expression as basis for creating this grammar

I made a right-linear grammar from a regular expression: The alphabet is: $Σ = \{a, b, c\} $ Regular expression: $r = cc^{*}(ba)^{*}bb$ My solution, it seems a little too short like I'm leaving ...
1
vote
1answer
733 views

Regular expression for a string not containing a set of substrings

I'm trying to figure out how to build a regular expression for a language that doesn't contain strings that contain $101$ or $001$. The alphabet is defined as $\{0, 1\}$. I'm stuck on trying to figure ...
1
vote
1answer
35 views

Constructing regular expressions with given substring requirments

I'm having trouble with this question about regular expressions: Let $L_1$ be the language of passwords containing at least one lowercase letter, at least one uppercase letter, and at least one ...
-1
votes
1answer
885 views

Regex for all odd length string that contains exactly 2 0's with language {0,1}

I just started learning about formal lang and automata theory, and recently learned about regex, so I don't know any complicated symbols, so please stick with basic symbols. The question is: Write a ...
3
votes
2answers
587 views

What is a regular expression that matches all strings over the alphabet except a particular substring?

I've come across this problem in my studies, and I've abstracted it to the more general case here. Given a finite alphabet, what is a regular expression that matches all strings over the alphabet, ...
0
votes
2answers
2k views

Convert regular expression to DFA

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

Can the plus operator in regex be replaced by the star operator?

Full disclosure, I'm interested in what this means about transformations on NFAs, but regex expressions seem like a easy way to ask the question. If you have a regex that uses the plus operator ...
4
votes
1answer
154 views

Equivalence of regular expressions [duplicate]

Is it possible, in general, to determine whether two regular expressions admit the same set of strings? Also, in particular, is it possible to determine whether a given regular expression admits the ...
2
votes
1answer
136 views

Are HTML and CSS regular languages?

I have a question whether or not CSS and HTML are regular languages. I believe CSS is a regular language, since it should be possible to create a regular expression to match the structure of CSS. ...
1
vote
1answer
98 views

A regular expression for strings with at most one triple of adjacent zeroes

I am trying to come up with a regular expression for the following language: The set of all strings with at most one triple of adjacent 0s. What does "triple of adjacent 0s" mean? Does it mean ...
1
vote
1answer
123 views

Can we minimise regular expressions using known DFA minimisation algorithms?

Of course, converting NFA to DFA is not a problem. But what about the other direction? My motivation is the notion of minimization regular expressions using the DFA minimization algorithm.
5
votes
2answers
208 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 ...
2
votes
1answer
2k 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 ...
0
votes
4answers
3k views

Regular expression for the strings without a particular substring

How can we design a regular expressions without particular substrings. The goal of this is to create language L which won't contain a particular substring (i.e. ...
1
vote
1answer
62 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
134 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
279 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
165 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
352 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
109 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$. ...
6
votes
3answers
75 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 ...
4
votes
3answers
103 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
133 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
118 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 ...
3
votes
1answer
1k 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
151 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
244 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: ...