Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
672
questions
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 ...
