I am looking for a proof that $(L_1^* L_2^* L_1^*)^* = (L_1 \cup L_2)^*$. I can reason on a case-by-case basis that for string in $(L_1 \cup L_2)$, that string also exists in $(L_1^* L_2^* L_1^*)$ and I know that the Kleene star operation is just recursive concatenation. I can also see that on that basis, if I then take the Kleene star of either language, I take any string in $(L_1 \cup L_2)^*$ and also form that string in $(L_1^* L_2^* L_1^*)^*$, but since there are possibly strings in $(L_1^* L_2^* L_1^*)$ that do not exist in $(L_1 \cup L_2)$, I am having difficulty reasoning about why they are equivalent in the case of Kleene star being applied to both other than by intuition. I'm also having trouble with formalizing the reasoning that I do feel sure about into a proof. Any help is much appreciated. Thank you.
2026-03-25 17:39:17.1774460357
Proof that for any two languages, $(L_1^* L_2^* L_1^*)^* = (L_1 \cup L_2)^*$
112 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
There are 1 best solutions below
Related Questions in ELEMENTARY-SET-THEORY
- how is my proof on equinumerous sets
- Composition of functions - properties
- Existence of a denumerble partition.
- Why is surjectivity defined using $\exists$ rather than $\exists !$
- Show that $\omega^2+1$ is a prime number.
- A Convention of Set Builder Notation
- I cannot understand that $\mathfrak{O} := \{\{\}, \{1\}, \{1, 2\}, \{3\}, \{1, 3\}, \{1, 2, 3\}\}$ is a topology on the set $\{1, 2, 3\}$.
- Problem with Cartesian product and dimension for beginners
- Proof that a pair is injective and surjective
- Value of infinite product
Related Questions in PROOF-WRITING
- how is my proof on equinumerous sets
- Do these special substring sets form a matroid?
- How do I prove this question involving primes?
- Total number of nodes in a full k-ary tree. Explanation
- Prove all limit points of $[a,b]$ are in $[a,b]$
- $\inf A = -\sup (-A)$
- Prove that $\sup(cA)=c\sup(A)$.
- Supremum of Sumset (Proof Writing)
- Fibonacci Numbers Proof by Induction (Looking for Feedback)
- Is my method correct for to prove $a^{\log_b c} = c^{\log_b a}$?
Related Questions in REGULAR-LANGUAGE
- Converting CFG to a regular expression
- How to approach regular languages using the pumping lemma?
- How to prove by induction that a string is a member of a recursively defined language?
- Formally expressing regular expression
- Deciding wether a language is regular, in the arithmetic hierarchy
- How to derive the set notation from regular expressions?
- Given language, say if it is regular, context-free and proove it.
- Given L1 is regular language and L1△L2 is regular is L2 regular?
- Proving a Language is Regular via Automata
- How to prove that a transformed language is regular using an NFA
Related Questions in FINITE-AUTOMATA
- Infinite strings and infinite theorems - Is there a theory on these stuffs?
- For any regular expression for a finite automata, how do you find the shortest word accepted?
- Converting NFA to DFA and then to regular expression.
- Divisibility problem using DFA
- Epsilon and phi in automata
- Did I find the right expression for the regular language for this FSA?
- Context free grammar to NFA
- Unable to construct Context-free Grammar from Pushdown Automaton $a^n b^m$
- CFG and Regularity of Two Language?
- Show that A/B is regular.
Trending Questions
- Induction on the number of equations
- How to convince a math teacher of this simple and obvious fact?
- Find $E[XY|Y+Z=1 ]$
- Refuting the Anti-Cantor Cranks
- What are imaginary numbers?
- Determine the adjoint of $\tilde Q(x)$ for $\tilde Q(x)u:=(Qu)(x)$ where $Q:U→L^2(Ω,ℝ^d$ is a Hilbert-Schmidt operator and $U$ is a Hilbert space
- Why does this innovative method of subtraction from a third grader always work?
- How do we know that the number $1$ is not equal to the number $-1$?
- What are the Implications of having VΩ as a model for a theory?
- Defining a Galois Field based on primitive element versus polynomial?
- Can't find the relationship between two columns of numbers. Please Help
- Is computer science a branch of mathematics?
- Is there a bijection of $\mathbb{R}^n$ with itself such that the forward map is connected but the inverse is not?
- Identification of a quadrilateral as a trapezoid, rectangle, or square
- Generator of inertia group in function field extension
Popular # Hahtags
second-order-logic
numerical-methods
puzzle
logic
probability
number-theory
winding-number
real-analysis
integration
calculus
complex-analysis
sequences-and-series
proof-writing
set-theory
functions
homotopy-theory
elementary-number-theory
ordinary-differential-equations
circles
derivatives
game-theory
definite-integrals
elementary-set-theory
limits
multivariable-calculus
geometry
algebraic-number-theory
proof-verification
partial-derivative
algebra-precalculus
Popular Questions
- What is the integral of 1/x?
- How many squares actually ARE in this picture? Is this a trick question with no right answer?
- Is a matrix multiplied with its transpose something special?
- What is the difference between independent and mutually exclusive events?
- Visually stunning math concepts which are easy to explain
- taylor series of $\ln(1+x)$?
- How to tell if a set of vectors spans a space?
- Calculus question taking derivative to find horizontal tangent line
- How to determine if a function is one-to-one?
- Determine if vectors are linearly independent
- What does it mean to have a determinant equal to zero?
- Is this Batman equation for real?
- How to find perpendicular vector to another vector?
- How to find mean and median from histogram
- How many sides does a circle have?
Hint: you know how to prove that $(L_1 \cup L_2)^* \subseteq (L_1^*L_2^*L_1^*)^*$. For the opposite direction, prove that $(L_1^*L_2^*L_1^*) \subseteq (L_1 \cup L_2)^*$. Then note that for any $L$, $(L^*)^* = L^*$.