Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
693
questions
0
votes
1answer
54 views
How to describe the language of an automaton in plain English?
How do I describe the following automaton in plain English?
The only thing that I can think about when explaining in plain English would be the states, alphabet, start, accepting state, but I think ...
-1
votes
0answers
25 views
How to check whether a language is regular or not? [duplicate]
I am given expressions such as
\begin{align}
L_2 &= \{ a^n b^{n!} \}, \\
L_3 &= \{ abcva^n \mid v \in \{a,b,c\}^*, n \in \mathbb{N}, n \text{ is even}, |v|=n/2 \}.
\end{align}
0
votes
1answer
19 views
Simplification of regex
I have a regex $R=\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)$ which has to be simplified by algebraic operations. As we can do,
$\epsilon+1+(\epsilon+1)(\epsilon+1)^*(\epsilon+1)=\epsilon+1+(\...
-2
votes
0answers
15 views
The set of all strings of 0’s and 1’s such that no prefix has more 1’s than 0’s [duplicate]
What strings does this represent? Is it saying that the first half of the string can't have more ones than zeroes? If that's the case what do we do with an odd length string?
-1
votes
0answers
28 views
Interpretation of $(a+ab)^*$
We know that $(a+ab)^*$ is the regex for the strings containing only $a$ or strings in which $b$ cannot appear consecutively.
\begin{align}
(a+ab)^0 &=\{\epsilon\}\\
(a+ab)^1 &=\{a,ab\}\\
(a+...
1
vote
3answers
85 views
Proving $(a + ab)^*a = a(a + ba)^*$
Need to prove $(a + ab)^*a = a(a + ba)^*$ by using regular algebra.
Concatenation does not commute. So repeated use of commutativity will fail. I am getting confused about which identity I should use ...
0
votes
0answers
32 views
Regular identity proof or disproof
I have to prove or disprove the following identities:
$(RS+R)^*RS=(RR^*S)^*$
$(R+S)^*S=(R^*S)^*$
$S(RS+S)^*R=RR^*S(RR^*S)^*$
So what I tried:
Not same because LHS cannot generate $\epsilon$ while ...
0
votes
1answer
45 views
Describe regular expression
I am learning about regular expression, and trying to describe a regular expression for the language L
$\qquad L = \{a^i b^j c^k \mid i+j = k\}$
What is the right approach and how to describe a ...
1
vote
1answer
32 views
Regex for strings with even number of 1's and number of 0's divisible by 5
I was trying to build up this regex but I am having huge expressions but nothing generates the given regex. I tried to break up the regex as
$0$ multiple of five times and odd $1$'s
$0$ multiple of ...
0
votes
1answer
23 views
Regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$
Design a regular expression for the language accepting the strings containing at most one pair of $1$'s over $\{0,1\}$
So basically we have the language $L=\{11,011,110,0011,1100\ldots\}$.
I find the ...
0
votes
1answer
13 views
Regular set corresponding to regular language
I have just started learning regular expressions and I don't have anybody around me to help me building conceptions. So I rely on online mediums. My question is whether every regular set corresponds ...
5
votes
1answer
43 views
Can a non-regular language $L$ have a non regular $L^*$?
I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?
0
votes
3answers
128 views
How many languages are described by a regular expression?
How many languages can a Regular Expression describe is it only one or infinite?
I have tried to google it but i haven't found any answer?
I know that a Regular Expression describes a Regular Language?...
0
votes
1answer
30 views
Conditions for an Language to be infinite
given 'r' , a regular expression that does not include λ or ∅, What are the Conditions of 'r' so that L(r) would be infinite?
-1
votes
1answer
31 views
Prove that given 2 regular expressions represent the same language
Is it possible to use regular expression identities to prove or disprove that the RE1=0*(0+1)*0* and RE2=(0+1)* represent the ...
-2
votes
1answer
35 views
Regular expression for binary representation of even numbers?
I need help writing the regular expression over the alphabet (0,1) represent the even numbers in base ten. So basically the regular expression would show represent an even number in binary. (also if ...
0
votes
0answers
28 views
Convert the Finite Automata (FSA) into its equivalent regular expression, using stepwise minimization
I was doing an assignment of Theory of automata but while doing this question I am stuck there is no such state that can be eliminated even from transition table. I am very confused and stuck please ...
1
vote
1answer
47 views
Proof regular languages are closed under homeomorphism
Let $\Sigma_1 , \Sigma_2$ be alphabets. Let $L\subseteq \Sigma_1^*$ be a regular language, and let $ h:\Sigma_1^* \rightarrow \Sigma_2^* $ be a homomorphism.
Proof $h(L)$ is regular.
I have written a ...
0
votes
0answers
25 views
Is language decideable (subset)?
I'm working on a proof for following question
$L=\{(R,S)\mid \text{R,S are regular expressions and } L(R)\subset L(S)\}$. Show that this language is/isn't decidable.
A language is decidable iff we ...
0
votes
2answers
36 views
Proving that a language defined by a regular expression is equivalent to a right linear grammar
After thinking for a bit, I am not able to prove a double inclusion proof for the following problem. It seems very interesting to me.
Consider the regular expression $r= ((1(00)^∗1 + 0)1)^∗$ and the ...
1
vote
1answer
18 views
How to prove the existence of the spectral expander with the given parameteres?
I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs:
$$
(1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0....
0
votes
0answers
36 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
33 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
34 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
53 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
47 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
44 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
32 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
106 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
34 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
20 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
46 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
53 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
34 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
31 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
26 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
15 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
27 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
32 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
28 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
86 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
21 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
42 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 ...
