Questions tagged [regular-expressions]
Questions about regular expressions, a formalism to describe regular languages.
708
questions
0
votes
0answers
27 views
Regular expression for all words over $\Sigma$ in which at least one symbol is missing
I have to consider the language $L$ on the alphabet {a,b,c,d}$ given by the words where at least one symbol of the alphabet is missing.
For example: abcccaca and bdadadaddb are accepted, but ...
0
votes
0answers
21 views
DFA and RE find out the language. Please can you explain?
Find the regular expression describing following languages over alphabet {0, 1}*.
...
2
votes
1answer
74 views
What is the regular expression for the language, {w | w does not contain the substring 11}
{w | w does not contain the substring 11}
What I am thinking: $(0^* 1 0^* )^*$
Is anything wrong with my expression?
Thanks in advance for your help!
0
votes
1answer
41 views
Simplifying the Language of this DFA
Above's the DFA in question (Sipser, Page 36). I have obtained the language of this DFA to be 0*1(1+00+01)*. But Sipser's textbook goes on to explain that the language of this DFA is (0+1)*1(00)*. But ...
1
vote
0answers
24 views
Is non-equivalence of regular expressions with union, concatenation and squaring NEXPTIME-hard?
On wikipedia, page about EXPSPACE it says
An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular expressions represent different languages, where the expressions ...
0
votes
0answers
34 views
Is my regular expression correct for this question?
IBM has decided that all sequences of numbers (such as mobile numbers) must be ordered in such a way that any mobile number is followed by at least 2 corporate numbers, and any landline number is ...
-1
votes
1answer
28 views
High Level description of Turing Machines
How can create a Turing machine that checks whether or not an input string is a well-defined regular expression? For example, it recognizes a language that consists of string over {0,1} and the ...
0
votes
0answers
52 views
Are the regular expressions equivalent?
Is the following equivalence true?
$$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$
I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.
-1
votes
2answers
46 views
Are this languages can be represented by regular expressions?
The set of all words with the same number of 0’s and 1’s.
The set of all words contained in {0,1}* that have an even number of 0’s and an odd number of 1’s.
I guess first one is NO.
Second one seems ...
-1
votes
1answer
27 views
How do I solve regular expression expansion when I have "+" sign?
For example, I am given this and my output is:
11+11* = 11, 1, 11, 111, 1111, ......
Since + means or sign, my logic is:
11 appears once or more
Then I work on solving 11*
Is it perfect?
Thanks.
0
votes
1answer
27 views
Does finding a reversal of a regular expression by automata need automata to be a DFA?
If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?
0
votes
1answer
67 views
Which of the following languages can be represented by regular expressions?
The set of all words contained in $\{0,1\}^*$ that have an even number of 0’s and an odd number of 1’s.
I came to discover that it is possible but not sure how. Can anyone express it in a regular ...
0
votes
0answers
46 views
How to carry out expansion in regular expression problems like ((0*10)*)?
I have been given some problems like:
Determine if each of the following strings belongs to the corresponding regular language.
i. ‘10100010’ and L((0*10)*).
iv. ‘011100101’ and L(01*10*(11*0)*)
I ...
2
votes
1answer
27 views
Minimal state DFAs for a regular expression of length $n$
I know that given any regular expression, we can find always find a minimal DFA which accepts the language it describes. However, this process can take up to exponential time and space. I'm wondering ...
0
votes
1answer
72 views
Simplify $R:=0^*+0^*1\left(1+000^*1\right)^*0^*$
I'm trying to simplify the following REGEX:
$$R:=0^*+0^*1\left(1+000^*1\right)^*0^*$$
$R$ is the result of transforming a GNFA that recognizes $L:= \{w \in \{0,1\}^* | \left(\forall \ i \in \left[1,|w|...
0
votes
1answer
41 views
Prove $(aa^*bb^*)^*=ϵ+a(a+b)^*b$ using regex laws
I tried to prove this by starting at RHS:
$$ϵ+a(a+b)^*b = ϵ+a(a^*b^*)^*b$$
But I dont know how to convert $(a^*b^*)^*$ to something else that will be helpful.
Any ideas?
1
vote
2answers
66 views
An integer (a string of digits) is $\text{/[0-9][0-9]$\ast$/}$. (Why isn't it just $\text{/[0-9]$\ast$/}$?)
I am currently studying the textbook Speech and Language Processing, 3rd edition (draft), by Jurafsky and Martin. Chapter 2.1.1 Basic Regular Expression Patterns says the following:
The regular ...
-3
votes
1answer
51 views
How can I convert from DFA in to regular grammar?
I have following information.
0 1
-> *q0 q0 q1
q1 q1 q2
q2 q2 q0
I have to convert this in to a regular grammar.
I wrote this:
...
-3
votes
1answer
34 views
How can I convert a Grammar to NFA?
Hello I have a task where I´m stucking at.
I have to convert a Grammar to NFA. I have these information:
G=(V,T,P,S) V={S}, T{0} and
S -> 0S
S -> 0
I can´t ...
0
votes
1answer
82 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 ...
0
votes
1answer
21 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+(\...
1
vote
3answers
92 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
50 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
58 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
27 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
15 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
78 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
130 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
42 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
39 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
59 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
42 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
46 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
37 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
64 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
55 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
60 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
33 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
182 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
67 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
22 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
55 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 ...
3
votes
1answer
89 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,...
