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

learn more… | top users | synonyms (2)

2
votes
6answers
175 views

Regular expression (ab U a)* to NFA with two states (Sipser)?

In the 3rd edition of Sipser's Introduction to the Theory of Computation (example 1.56, p.68), there is a step-by-step procedure to transform (ab U a)* into a NFA. And then the text ends with: "In ...
1
vote
1answer
47 views

Convert DFA to Regular Expression

In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The q_2 state is eliminated first. The provided solution to eliminate q2 is: ...
-2
votes
1answer
41 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
2
votes
1answer
37 views

Is it possible to repeat a wildcard in regex?

.{5} would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character." The immediate way that ...
0
votes
1answer
46 views

Convert regular expression to Automaton

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: ...
0
votes
3answers
112 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
1answer
70 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: ...
0
votes
2answers
42 views

Recognizing a language given a Automata

I'm trying to figure out which language can be recognized in this automaton According to wikipedia here "The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted ...
2
votes
3answers
77 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 ...
4
votes
1answer
127 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 ...
0
votes
2answers
90 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 ...
1
vote
1answer
55 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 ...
3
votes
1answer
59 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
89 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
95 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
158 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
65 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
55 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
43 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
105 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
76 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
71 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
62 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
807 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?
15
votes
1answer
342 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
83 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
333 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
155 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
24 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
471 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
61 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
96 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
79 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
46 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
86 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
62 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
826 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
37 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
1k 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
694 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
299 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
247 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
172 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
105 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
132 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
236 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 ...
3
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
4k 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
67 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 ...