Questions tagged [regular-expressions]
Regular expressions or Regex is a search pattern for strings defined by a sequence of characters.
668
questions
1
vote
1
answer
45
views
Is the Language $L = \{a^n b^m c^k d^q e^r \,|\, n, m, k, q, r \geq 0\}$ a Valid Regular Language?
I am inquiring about the nature of language L. It appears that L is not categorized as a regular language due to its unique characteristics, which involve the need to count occurrences of multiple ...
- 378
0
votes
0
answers
19
views
regex for exactly n possible values which are unique
I want to write a regular expression in my python code, but I think this is more of a mathematical challenge.
So my requirement is, suppose I want to create $3$ unique coupon codes, I can write a ...
- 101
-1
votes
1
answer
16
views
Prove that the Kleene closure of the union between language and null string is the same as the Kleene closure of just the language [closed]
There's something I'm currently stuck on.
Suppose there is a language L. We know that L* is {ε, L, LL, ...} and so on.
(L+ε)* should produce the same set since the null string is already accounted for ...
- 1
0
votes
1
answer
28
views
Express a count of an element in period of time [closed]
I want to know if it is possible to represent the count of an element in a set, having different elements collected over a given period of time.
Let's say $A$ is the set with varying elements at a ...
- 13
0
votes
0
answers
22
views
Pumping lemma question: L = {w0nw | w є {0,1}* and n > 0} verification
Consider the language L = {w0nw | w є {0,1}* and n > 0}. Check the alternative containing the choices that we can make regarding the parameters of the pumping lemma in order to prove that L is not ...
- 1
0
votes
1
answer
43
views
Is there a name for the set of single-character prefixes of words in a regular language
This question concerns regular languages and regular expressions.
Suppose we have an alphabet $\Sigma$ and a language $\mathcal{L}$. For some algorithm, I am particularly concerned with the set of ...
- 1
0
votes
1
answer
48
views
Find all strings of $w$ that satisfy following equation
Solve the following string equation on the alphabet $A = \{1, 0\}$ and find all $w$'s:
$w011 = 011w$
- 11
0
votes
0
answers
32
views
Trying to draw a graph from regular expression
I do my homework
My regular expression is
$b^m\,(ab)^na | m,n >= 0$
After several attempts I have this:
The vertex q1 is the entry and q2 is the exit.
Do you think it corresponds to the given ...
- 11
2
votes
0
answers
71
views
Are $111^*$ and $11^*1$ equivalent?
I know it is a trivial question but are $111^*$ and $11^*1$ equivalent? (I think yes because I can have 11 in both at minimum but that seems odd to be true). I am trying to understand automata theory ...
- 21
0
votes
0
answers
51
views
Regular expression .Find it
Construct a regular expression that defines the language of all words that contain either the aa-substring or the bb-substring but NOT BOTH the aa-substring and the bb-substring in the same
word....
0
votes
2
answers
69
views
Superscript in regular expression
If I want a language where the entries are in the form of $\gamma A^{n+2}\gamma A^{n+2}...\gamma A^{n+2}$, is it possible to write a regular expression as $(\gamma A^{n+2})^*$, or is it weird to have ...
- 3
0
votes
1
answer
24
views
Context-free language as regular expression
I want to ask a short question. Can a regular expression expresses a context-free language that is not a regular language?
- 3
1
vote
1
answer
51
views
Prove equivalence of two regex using basic identities.
I'm trying to prove the following identity
$$
(x+y)^* = (x^*y)^*x^* = x^*(yx^*)^*
$$
Using the following 12 identities
$L + M = M + L$
$(L + M) + N = L + (M + N)$
$(LM)N = L(MN)$
$\emptyset + L = L + ...
- 333
1
vote
1
answer
30
views
Infinite number of regular exressions for a given language
Took a Theory of Computation exam where one of the questions was :
Is there an infinite amount of regular expressions for the language $L=\{aa,bb\}$ ?
The proof requested was just an informal one.
My ...
0
votes
1
answer
885
views
The set of all strings of 0's and 1's not containing 101 as a substring
I'm working through a textbook on automata theory (Introduction to Automata Theory, Languages, and Computation) and I'm stuck on the Exercise 3.1.3:
Write regular expressions for the following ...
0
votes
1
answer
797
views
A regex that matches strings containing an even number of 0’s or even number of 1’s
I need to write a regex that matches strings containing an even number of 0’s or even number of 1’s. (Alphabet Σ= 0,1)
I have already tried ...
- 9
1
vote
0
answers
38
views
Regular Expression Identities list?
I have been working on problems to simplify or equate certain regular expressions to others but so far the list of identities I have found in my textbook (Sipser) doesn’t tell me enough to simplify ...
- 279
1
vote
2
answers
307
views
Finding the set of strings over {𝑎,𝑏} that ends with an odd number of "a"s
I need to write a regular expression that identifies the set of all
possible strings over Σ={𝑎,𝑏} that end with an odd number of "a"s.
I'm getting better with regular expressions, but ...
- 119
0
votes
0
answers
78
views
Regex groups and complements
Not sure about the "math" language of that but ill try to explain my question:
Assume we have two regexes A, B. I say Regex ...
- 1
0
votes
1
answer
29
views
Regular expression extraction from alphabet
I have this Alphabet Σ = {k,l} so I do not understand how I can find the words equal bigger than 3
≤3 in L ((k|l)l*), should I use the words with 3 letters always starting with k or somthing else?
- 3
0
votes
2
answers
385
views
A regular expression for all strings over ${1, 0}$ which do not have $111$ as a substring
Would the following be a correct regular expression for this?:
$$(0 + 01 + 011)^* + (0 + 10 + 110)^* + (1 \cdot (0 + 01 + 011)^*) + ((0 + 10 + 110)^* \cdot 1) + 11 + 1$$
My thought process is I broke ...
- 201
3
votes
0
answers
79
views
What is the formal definition of a combinational logic?
Question Background
A finite-state machine can be defined as a 5-tuple as follows (Sipser, pg. 35):
The image below (taken from the Wikipedia article on autamata theory) seems to suggest that ...
- 161
0
votes
1
answer
43
views
Confusing about regular expressions.
I am new to regular expressions. Hence, it is a bit confusing to me. If I have a regular expression such that $(AAAA^{*}X)^{*}AAAA^{*}$, does $g=AAAAXAAAXAAAAXAAA$ can be one of the expressions? Also, ...
- 3
0
votes
1
answer
93
views
Create regular expression not contain "aaa"
I have a question about creating regular expression out of the given language.
The language is : 𝐿3 = {𝑤∈{𝑎,𝑏,𝑐}∗|𝑤 𝑑𝑜𝑒𝑠 𝑛𝑜𝑡 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑎𝑎𝑎}
I'...
- 15
0
votes
0
answers
26
views
Converting the optional ? and plus + REGEX quantifiers to NFAs
I am trying to find a general way of converting the ? and + Regex operators to NFAs.
I tried to draw an NFA for a+ and a? and got the following:
NFA of a+ and a?
Is what I'm doing making sense?
- 1
1
vote
1
answer
62
views
Determine if language $L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$ is regular
Question.
Determine if the language is regular:
$L=\{xyxz\,\,|\,\,x\neq\varepsilon,\,\,x,y,z\in\{0,1\}^{*}\}$
I think $L$ is non regular, because of the second x.
I'm trying to prove with the ...
- 387
0
votes
1
answer
53
views
Determine if language is regular
Question.
Determine if the languages are regular:
$L_{1}=\{(ab)^{k}a(ba)^{k}\,|\,k\geq0\}$
$L_{2}=\{(ab)^{k}b(ba)^{k}\,|\,k\geq0\}$
I think both are not regular, I used the Pumping Lemma to prove, ...
- 387
0
votes
1
answer
65
views
Prove that the language is not regular without using the Pumping Lemma
Question.
Prove that the language is not regular without using the Pumping Lemma:
$L=\{a^{n}b^{m}c^{k}\,\,|\,\,n^{2}+m^{2}=k^{2}\}$
Attempt.
I assume that L is regular, and I am trying to use ...
- 387
0
votes
0
answers
53
views
Find regular expression for a given language $L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$
Question.
Write a regular expression for the language:
$L=\{0^{n}1^{m}\,\,\,|\,\,\,n+m(mod3)\neq0\}$
Attempt.
$r=(000)^* (0(ε+0+1+011)+1(ε+1)) (111)^*$
Is my regular expression correct? If so, is ...
- 387
0
votes
0
answers
128
views
Complement of a regular expression
Question.
Write a regular expression for the languages:
all words in $\{a,b,c\}^{*}$ in which $a$ instance is followed by a sequence of at least two $c's$
The complement language of $1$
Attempt.
$\...
- 387
0
votes
0
answers
39
views
Regular language that specifies cycles of length 7 for rule 110
I found a language of which I may assume that it is regular, and now I want to know the grammar.
The words $w$ of the language have the form (A [0, 2, 4] B C+)+ ...
- 17.9k
-1
votes
1
answer
31
views
Symbol raised to the power of asterix raise to the power of asterix in regex [closed]
To describe the regex (a*+b+a)* in plain English you would simplify it to (a*)* + (b)* + (a)* . How would you describe (a*)* in English as the rest is just any number of bs or any number of as?
- 101
0
votes
0
answers
53
views
Is there a procedure to give a generating function for arbitrary regular languages?
The Schützenberger methodology can enumerate the number of words of given length $k$ for unambiguous context free languages by a generating function. But not all regular languages are unambiguous ...
- 17.9k
0
votes
1
answer
31
views
How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?
How to prove that for any $w_1,...,w_n \in \{0,1\}^*$ regular expression $w_1^*w_2^*\dots w_n^*$ doesn't represent language $\{0,1\}^*$?
- 315
0
votes
0
answers
47
views
Is b*a(a+b)* equivalent to (a+b)*a(a+b)*?
So two regular expressions are equivalent if they are associated, i.e., produce the same regular language, I am curious about this because it is clear that the language produced by $b*a(a+b)*$ is ...
- 51
1
vote
0
answers
65
views
Unambiguous regular expression for binary strings
Give decompositions that uniquely create the following sets of 0/1-strings.
All strings with no odd blocks of length greater than 4.
With this problem, I was looking for a regular expression that ...
- 21
0
votes
0
answers
59
views
Can a binomial be a term?
This is probably a silly question but I'll ask anyway. I know that terms in mathematics are numbers or variables or some combination of numbers/variables multiplied by each other. They are combined ...
- 11
0
votes
2
answers
71
views
What happens if I expand b*( (ab) b* )*? [closed]
I just wanted to confirm if what I have here is correct. If I expand b*((ab)b*)* are these set of strings valid? Sorry, I tried posting it in StackOverflow but that needed code and this doesn't ...
- 63
1
vote
0
answers
28
views
Substitution of a letter with a regular expressions in regular expressions identities
There is an exercise in "Introduction to computer theory" by Daniel IA Cohen (ch. 4, ex. 20) the main part of which goes like:
Explain why we can take any pair of equivalent regular ...
- 559
0
votes
1
answer
36
views
Prove formal language isn't regular
I've been tasked with showing that given a regular language $L$ over $\Sigma={0}$, prove that the language $Minus(L)= \{ 0^x1^y | 0^{x-y}\in L \}$ is not regular.
I've tried to use $L=0^*$, which ...
- 401
1
vote
1
answer
45
views
Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}:
Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}:
L = {w : w does not contain aaab}.
For this task, you also need to build a deterministic finite automaton, but I ...
- 11
1
vote
0
answers
64
views
Finding equivalence class for $R_L$ of a regular language
Let $\Sigma = \{ a, b, c\}$,
$$
L = \{w\in\Sigma^*\mid w \text{ starts with $ab$ and ends with $ab$}\},
$$ i.e. $L = ab(\varepsilon + (a+b)^*ab)=ab+ab(a+b)^*ab$. I need to find a regular expression ...
- 383
0
votes
1
answer
573
views
Prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
I'm currently trying to prove that $L=\{a^n b^l : n \leq l\}$ is not regular by pumping lemma
My proof:
If we choose $w$ such that $w=a^P b^P$, then since $|xy| \leq p$, $y$ must be $a^P$, meaning it ...
- 111
0
votes
1
answer
463
views
Regular Expression - binary digits, no occurrences of 111, solving methodology?
Can someone show in some simple steps how one goes about creating a regular expression from binary digits that excludes all occurrences of 111? What I am having trouble is how one starts these sorts ...
0
votes
1
answer
60
views
creating regular expressions from given language
The first question is $L_1 = \{w \in \{a,b,c\}^∗ \mid \text{$w$ ends with $ca$}\}$
I started by creating a DFA for that for better understanding and then making a regular expression.
and the regular ...
- 15
0
votes
1
answer
42
views
Finding the equivalent regex for a formal grammar
We have the following formal grammar:
$a, b$ are terminal symbols.
$S, A, B$ are non-terminal symbols.
$S$ is the startsymbol.
Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
- 307
1
vote
1
answer
475
views
Regular Expression for binary string that contains number of zeros not a multiple of 3
I want to generate a regular expression by using only + (or, union), * (0 or more), and (^+ 1 or more) operations.
The language contains only 0 and 1. The problem is to generate a regular expression ...
1
vote
1
answer
36
views
Solution Verification: Regular expression that starts with $a$ and doesn't contain $aba$ pattern.
Write a regular expression that starts with $a$ and doesn't contain $aba$ pattern.
My Solution:
If my expression doesn't contain $aba$, then it must not have a $b$ alone in the middle of it before ...
- 2,103
1
vote
2
answers
59
views
Constructing grammar for $a^ib^j$ / $i\neq j$
I want to construct a grammar for the following regular expression: $a^ib^j / i \neq j$. I did it the following way:
$S_1 \rightarrow aaSb | aaAb$
$A \rightarrow aA | \epsilon$
$S_2 \rightarrow aSbb | ...
- 491
2
votes
1
answer
2k
views
a^m b^n c^n prove it's not regular/pumping lemma
How to prove that $L = \{a^mb^nc^n \mid n, m \geq 0\}$ is not regular by the pumping lemma
My attempt:
Let's suppose $L$ is regular.
There exists a pumping constant p, and we choose $w = a^pb^pc^p$
...
- 491