# Questions tagged [regular-expressions]

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

573 questions
Filter by
Sorted by
Tagged with
314 views

### Build a regular expression to define a regular language [duplicate]

The language is an infinite set of chains that are defined by the next conditions. Conditions: ...
3k views

### Build a regular grammar for a regular language [duplicate]

The language considered is the infinite set of all chains that meet the following conditions. Conditions: ...
191 views

### Convert regular expression to Automaton [duplicate]

I'm trying to construct a finite-state automaton from the following regular expression: $$(a|ba)(a|ba)^*(b|ab)^*$$ I know that from $$(a|ba)$$ the automaton should look something like this: ...
141 views

### What is the regular expression to the given language?

I can't really find out, how can the following given Language be written down with regular expressions $L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \}$ I had some guesses, but I don't know ...
946 views

### Complexity of bitwise AND operation on bit string regular expressions

Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time ...
297 views

### Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable?

I have having trouble with the following question: Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.
228 views

### regular expression: sum of positive fixed point decimal numbers [closed]

I need help with this exercise. Indicate the regular expression for the following Languages. Explain your expression in one sentence and indicate the basis form of the alphabet. Indicate also every ...
577 views

### regular expression in license plates

I'm trying to write a regular expression for some particular license plates. They consist of one up to three capital letters, a hyphen, one up to two capitol letters and one up to four numbers. The ...
2k 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 (...
1k 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 ...
823 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: ...
164 views

1k 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 ...
2k 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 ...
98 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: ...
160 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 ...
258 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 ...
100 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=(aa)?(aa) and I convert it to a grammar: G ::= A B A ::= C | (...
4k 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 ...
660 views

2k 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 ...
123 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 ...
208 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$. ...