Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
123
votes
4answers
169k 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, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
5
votes
2answers
8k 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 ...
13
votes
3answers
23k views

How to create DFA from regular expression without using NFA?

Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that? I asked this question to our professor but he ...
12
votes
2answers
5k 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 ...
24
votes
2answers
1k 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 ...
2
votes
2answers
9k views

Convert regular expression to DFA

How do you construct a DFA from a language that has a + sign? e.g. $L = \{(a+b)\}*$
28
votes
4answers
4k 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 ...
8
votes
1answer
308 views

How hard is finding the shortest path in a graph matching a given regular language?

Suppose we are given a directed graph $G = (V, E)$ with edge weights $w : E \rightarrow \mathbb{R}$ (we can assume there are no negative cycles) and edge labels $\ell : E \rightarrow \Sigma$ from some ...
3
votes
5answers
47k 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. 110)...
16
votes
2answers
4k 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 ...
27
votes
1answer
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 ...
9
votes
1answer
560 views

When is a regexp is not a Regular Expression?

Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a regexp. As I said, a regexp, not a ...
0
votes
1answer
949 views

Regular expression of a language over {a,b,c} which does not contain substring bbb

I'm trying to figure out how to build a regular expression for a language that doesn't contain substring bbb. The alphabet is {a,b,c}. I'm trying to construct a DFA and convert to help me get the ...
3
votes
4answers
89k views

Regular Expression for even-odd language of string

I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'...
25
votes
6answers
6k views

What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had ...
8
votes
3answers
2k views

Why isn't it simple to count the number of words in a regular language?

Given a DFA, A, let L(A) denote the number of words A accepts. I think it's easy to calculate L(A): Translate the encoding of A into a regular expression. If the Kleene star appears anywhere in the ...
2
votes
1answer
4k 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 ...
7
votes
3answers
17k 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
228 views

Compare regex in programming languages with regular expression from automata/formal language?

I'm trying to reconcile the differences/similarities between regular expression from formal language theory and automata, and the "regex" offered by programming languages. These two differ not just ...
3
votes
1answer
56 views

Why $P$ cannot have NULL string in Arden's Theorem?

Arden's Theorem says that in the equation $R=Q+RP$, the $P$ cannot have NULL string. In this respect,the theorem will not be valid for the expression $R=Q+R(NULL+01)$. Am I correct? If so, then what ...
3
votes
1answer
89 views

Are there any specific mechanical ways to reduce a regular expression 'equation' to a more simple one?

So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact. Can we use some sort of ...
3
votes
2answers
384 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
2
votes
1answer
275 views

fixed point in regular expressions

I've posted this question first on StackOverflow but this section seems more suited for this kind of questions. Also I'm not trying to simply solve this exercise (it is a "parsing" exercise, once I'll ...
2
votes
2answers
166 views

Looking for an “intuitive” regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|...
2
votes
2answers
1k views

How to write regular expression excluding certain pattern aba from albhabet set {a,b}? [duplicate]

Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite? Is there any generic way to write a regular ...
1
vote
1answer
1k views

Write a regex to match string that does NOT contain a certain pattern [duplicate]

Let's say our alphabet is 0 and 1. How would you approach writing a regex to generate a language of words that do NOT contain 101. The only regex operators allowed are concatenation , star * and OR |...
1
vote
1answer
362 views

Finding regular expression for a language with more substring of one type than from another

Take the alphabet A={0,1} I need to build a regular expression for the language with less or equal substrings 011 than 110. I tried to figure out what would be the finite automata but I'm not to ...
0
votes
1answer
573 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 ...
0
votes
1answer
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"...
0
votes
3answers
4k 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: ...
0
votes
2answers
1k views

Describe in English the pattern in the following regular expressions

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
13
votes
1answer
12k views

Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
5
votes
1answer
20k views

Steps to convert regular expressions directly to regular grammars and vice versa

I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars): Then I came across many ...
9
votes
3answers
4k views

DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$

We can form DFA accepting binary numbers divisible by $n$. For example DFA accepting binary numbers divisible by 2 can be formed as follows: Similarly DFA accepting binary numbers divisible by 3 ...
26
votes
1answer
748 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 1)^*| ...
4
votes
1answer
2k views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
6
votes
1answer
107 views

Relative succinctness of NFAs and regular expressions

What is known about the succintness of NFAs, relative to regular expressions? In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the ...
4
votes
2answers
328 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 ...
11
votes
3answers
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 ...
10
votes
1answer
410 views

Constructing all context-free languages from a set of base languages and closure properties?

One way of looking at regular expressions is as a constructive proof of the following fact: it's possible to construct the regular languages by starting with a small set of languages and combining ...
5
votes
0answers
109 views

Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?

I have read that minimizing regular expressions is, in general, PSPACE-complete. Is it known whether minimizing regular expressions without the Kleene closure (star, asterisk) is in P? The language ...
4
votes
2answers
1k views

How is $\emptyset^* = \{\epsilon\}$?

I know that $\emptyset$ is a an empty language, i.e. language containing no string. A law involving empty language is: $\emptyset L = L\emptyset = \emptyset$ It correctly states that we cannot ...
3
votes
3answers
149 views

Are regular languages and their regular expressions part of computer science?

I am trying to understand if regular languages and their regular expressions are concepts of computer science in general and if these are discovered, or invented, by computer scientists, in particular....
2
votes
1answer
620 views

How do you convert a regular expression to its disjunctive normal form?

A regular expression $r$ is said to be in disjunctive normal form if it can be written in the form $r = r_1 +r_2 +\dots+r_n$ for some $n ≥ 1$, where none of the regular expressions $r_1, r_2, \dots, ...
1
vote
2answers
229 views

Is the language of words that contain a square regular or context-free? [duplicate]

$ L = \{w \in\{a,b\}^{*} : \exists_{x,y,z} , w=xyyz \wedge y \neq \epsilon \}$ I have a problem with this exercise. I need to determine if this language is regular, context-free or not both and ...
1
vote
1answer
349 views

How can I show context free grammars are strictly more expressive than regular expressions with an example?

I need to show a CFG can express everything that can be expressed by a regular expression, and something that cannot.. I have no idea what example is traditionally used for this.
5
votes
4answers
1k views

Does Thompson's algorithm produce optimal NFAs?

I'm using Thompson's algorithm to convert from a regular expression to a NFA. Is Thompson's algorithm guaranteed to always output a minimal NFA, i.e., a NFA with the smallest possible number of ...
4
votes
1answer
955 views

Recursive definition of a language given the regular expression

Consider the language: $$ L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\} $$ I know that there is a DFA that accepts this language, and furthermore, that the regular ...
4
votes
3answers
6k views

Write a regular expression - Contains an equal number of 01 and 10 subtrings

I'm trying to write a regular expression for the language $L\subseteq\{0,1\}^*$ of strings that begin with $0$ and contain an equal number of occurrences of the substrings $01$ and $10$. ...
3
votes
2answers
968 views

Showing Regular Languages are closed under removal of rightmost character

"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular." I tried going by closure properties of ...