Questions tagged [regular-expressions]

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

Filter by
Sorted by
Tagged with
0
votes
0answers
32 views

Showing that $(b^*a)^+.(b^*a) = (b^*a)^*$

I've been learning regular expressions as part of a class on automata and formal languages. I am still fine tuning and trying to figure out the algebra and the identities. I am struggling with the ...
1
vote
1answer
23 views

All strings that contain no run of a's of length greater than two for $\Sigma = \{a,b,c\}$

The solution to this problem is $$(b + c)^*+(b + c)^*((a + aa)(b + c)^+)^*(a + aa)(b + c)^*. $$ Isn't the $+$ sign a union between sets?, I am asking because I am viewing the line $(b + c)^*+(b + c)^*$...
1
vote
1answer
33 views

Simplifying $b(abb + abbbb + aba^*bbb)^*$

I'm having issues simplifying regular expressions. I can't find a method to approach this problem. How would I approach simplifying this regular expression: $$b(abb + abbbb + aba^*bbb)^*$$
2
votes
1answer
42 views

Is there a bound on possible Dead state in a minimized DFA

I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc? Intuitively, I am thinking that it ...
1
vote
2answers
28 views

Converting a regular expression to a context-free grammar

Does this conversion look right? I am learning conversion from RE to CFG. RE: $$(a \cup b)^* \cup ab(a \cup b)^*$$ CFG: Terminals: $$ S_1 \to a \\ S_2 \to b $$ This is for the first $(a + b)^*$: \...
3
votes
1answer
31 views

Worst-Case Complexity of Quantifiers in Thompson's Construction

My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the ...
0
votes
1answer
30 views

Regular expression for words longer than 2 containing at most two x-s

I want to make a regular expression for the language consisting of words whose length is at least 3 and which contain at most two $x$'s, that is, $$\{w\in \{x,y\}^* \mid |w|\geq3\text{ and the number ...
1
vote
2answers
62 views

Regular Expression and NFA: each block of five consecutive symbols contains at least two 0's

Consider the alphabet {0, 1}. How do I find the regular expression for the set of all strings such that each block of five consecutive symbols contains at least two 0's? Here, by block I mean a given ...
1
vote
1answer
23 views

Is the language of binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$ regular? [duplicate]

Consider the language: $L=$binary strings that contain a substring of the form $ww$, where $w \in (0+1)(0+1)^*$. I am convinced this language is not regular, as $w$ can have arbitrary length due to ...
0
votes
0answers
18 views

How to describe this language a* (ba (cf* (g ( f +h )* bf* )* e )* a* )* in words?

I was task to describe this regular expression a* (ba (cf* (g ( f +h )* bf* )* e )* a)* informally. My attempt at describing it informally = any number of a followed by any number of one b one ...
1
vote
2answers
40 views

Is $\{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ regular or not?

Show if $L = \{a^mb^nc^n \mid m,n \geq 0\} \cup \{b,c\}^*$ is regular or not. My attempt: I think the Pumping lemma won't work in that constellation, so I'm working with "The intersection of ...
2
votes
0answers
50 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
0
votes
0answers
18 views

Fixing changing characters a regular expression [duplicate]

I have a regular language $L$ from characters of $\Sigma_1$, we define: $\Sigma_2=\Sigma_1\cup \{+,-\}$ and $$L^{+-}=\left\{a_1\cdot p\cdot a_2\cdot q \cdot a_3\cdot\ldots \cdot a_k\mid a_1,a_2\ldots,...
0
votes
1answer
22 views

Give the Regular-Expression (NFA) with specific Separation Patterns

Question: Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's. Attempt: ...
1
vote
1answer
33 views

Doubt in understanding the time complexities of algorithms to recognize regular expressions

I was going through the text Compilers: Principles, Techniques and Tools by Ullman et. al first edition where I came across the following table. The authors justify the table as follows: Given a ...
0
votes
1answer
29 views

Regular set of the “does not contain” kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
1
vote
1answer
21 views

Equivalent regular expressions - Proof

I came across the following two regular expressions $r_1 = 0^+(10^+0)^∗0^*$ and $r_2 = 0^+(10^+0)^∗$. I know, in general, proving if two regular expressions are equivalent is hard in terms of time ...
1
vote
1answer
14 views

Can the lambda string be generated in any grammar?

I'm still quite new to regex, and I've seen topics online of people talking about removing lambda productions, but that has yet to be discussed in the class and the only formal definition of the rules ...
1
vote
0answers
20 views

Constructing an NFA that is equivalent to a regular expression

I am a little stuck at attempting to give an NFA for the regular expression $0^+(10^+0)^∗$ , where the alphabet is ${0, 1}$. I have tried to construct multiple NFA's state diagram and the closest I ...
-1
votes
1answer
26 views

Regular expression for the language $\{wtw^r \mid w, t \in\{0 \cup 1\}^+\}$

What is a regular expression for the language $C=\{wtw^r \mid w, t \in \{0 \cup 1\}^+\}$? Here $w^r$ is the reverse of $w$.
1
vote
1answer
18 views

Is it possible to build regex-based-map with search asymptotically faster then hashmap?

From time to time I stumble across a problem of matching hashmap keys to a regular expression. In such situations I am forced to loop through all of map's elements and try to match every single key to ...
1
vote
0answers
29 views

How to generate a context-free grammar that defines a regex expression

As the title says, I have been asked to generate a grammar that defines the language of regular expressions. The symbols are: + . * | ? char I tried and came up with this but it doesn't work when ...
0
votes
1answer
19 views

CFG of all regular expressions over a binary alphabet

I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), *, +, e} (e ...
1
vote
2answers
51 views

Constructing a NFA from a regular expression

I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression. I started by constructing the NFA ...
0
votes
0answers
19 views

If L is a regular language, then the particular L′ is also regular? [duplicate]

Show that if $L ⊆ Σ^∗$ is a regular language then the following language is also regular: $$L' = \{w\mid ∃x, y ∈ Σ^∗ : w = xy ∧ yx ∈ L\}$$ Can you give me a hint how to solve that?
9
votes
2answers
1k views

Theory behind regex implementations

In a 2007 article, Russ Cox (at presents, he leads the development of the Go programming language at Google) argues that regex engines in languages like Java, Perl, PHP, Python, Ruby are built on a ...
1
vote
1answer
32 views

Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

Is there any difference between saying $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $? I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$ my ...
1
vote
1answer
47 views

Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$

how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much.. $$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
1
vote
1answer
32 views

All strings in which every substring 000 appears after every 1

I found this given problem as follows: Write a regular expression where all strings in which every substring 000 appears after every 1. Now, I also found the answer from Illinois university study ...
2
votes
1answer
54 views

Formal Binary String Regular Expression (each pair of 00 must have 11 before it)

I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it. I realize this can be done with lookbehinds using the following ...
0
votes
3answers
65 views

(Finite Automata) Why the following is a NFA?

The first one seems like a DFA. Could someone explain why this is a NFA?
0
votes
0answers
16 views

Check if the regular expression r made up of the single symbol alphabet Σ = {a} defines language L(r) = a* [duplicate]

I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ ...
1
vote
3answers
57 views

Regular Expression for language [duplicate]

I have a grammer with the following productions, S -> aA | bC | b A -> aS | bB B -> aC | bA | a C -> aB | bS I have to construct regular expression for ...
0
votes
1answer
65 views

Conversion of RE to NFA

I've a question regarding this diagram. I'm thinking of adding a new state between q5 and q6 that accepts a lambda value but I'm not quite sure or this diagram is correct? And in what situation we add ...
-1
votes
2answers
90 views

Find language and regular expression

I don't know how to find the Language and the regular expression for each one. there are any special method for those kind of question?
0
votes
2answers
143 views

How do you read the regular expression (0^∗10^+)^+?

Give an example of a string in the language of $(0^*10^+)^+$. I've been asked to give an example of a string in this language but I'm confused on how to read this notation. I'm guessing the ...
0
votes
1answer
60 views

Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$

Hope you had a fantastic christmas break :) I am trying to find an algorithm in polynomial time that finds the shortest arithmetical expression (the one with the least amount of 1 symbols) to express ...
2
votes
1answer
131 views

Context Free Grammar to Regular Expression?

I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: &...
0
votes
1answer
43 views

If L is context free and R is regular then R – L must be context free?

Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language? The difference might be the CF part of the language left then it would be, but I'm not sure how ...
-1
votes
1answer
33 views

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1answer
31 views

Create an Finite Deterministic Automata for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
2
votes
1answer
88 views

Regular expression for all binary strings avoiding 0110

Consider the language $$ L = \{ w : w \in {0,1}^* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \} $$ What is a regular expression for this language? I thought of $1(1)^*0(0)^*$....
1
vote
2answers
69 views

Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular On this one I think I can ...
0
votes
1answer
39 views

How to check if a language is not regular?

I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression However, if the language is not regular i have to prove using the "...
0
votes
1answer
24 views

Relationship between Kleene Star of a subset of regular language and the regular language

If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
1
vote
0answers
55 views

How to prove a statement in regular expression?

I cannot figure out how to go about proving this statement in regular expression. $$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$ Here's what I have ...
0
votes
0answers
36 views

Regular expression for all binary words avoiding 11

I am reading a book example on regular expressions and I have a trouble to get why the answer is correct. "Write a regular expression for the regular language that contains all the strings by 0's ...
0
votes
0answers
23 views

All string matches for regular expression [duplicate]

Given a regular expression, the ask is to find all matches in a string, str. Most implementations give longest match only. For example, [\d]* in str "123456", the regex libraries in C++ or ...
0
votes
1answer
189 views

Convert finite automata to regular expression

I am trying find the regular expression that describes the finite automata in the image below. Given the following finite automata which of the following regular expressions describes the same ...
0
votes
0answers
10 views

I'm having some trouble converting a FA to a RegEx [duplicate]

I was reviewing some of the material that I found about FA to RegEx and while I was practicing with one or another conversion, I came across this FA that I could not pass to RegEx. Would someone be so ...

1
2 3 4 5
14