Questions tagged [kleene-star]
The kleene-star tag has no usage guidance.
44
questions
2
votes
1answer
105 views
Closure properties of Alternating Circuit 1 level
Recall that $\mathsf{AC^1}$ is the class of circuits with unbounded fan-in, polynomial size, and logarithmic depth.
Is this class closed under Kleene star?
I thought it would be simple since it is ...
0
votes
1answer
21 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)$?
3
votes
1answer
111 views
Why do we need two variables for implementing kleene star operation on a language using context free grammars?
I have a Context-Free Grammar (CFG) G which has a S for generating a language L. Now to produce a grammar for L*, another variable T (which is not present in the variable set of G) is taken and the ...
1
vote
1answer
45 views
Characterization about Kleene Closure, when is a language $L=L^*$?
I'm trying to find a characterization of when $L=L^*$.
I think I have one, but maybe is trivial, but I don't know if the proof is correct.
Claim: $L=L^* \Leftrightarrow L=LL$.
Proof:
If $L=L^*$ then ...
1
vote
2answers
94 views
How to prove that concatenating a language A and A* is commutative?
Suppose we have a language $A$. I want to prove that $AA^*$ is commutative. I know that this expression equals $A^+$, but I'm not sure how to go about a proof yet. This is my attempt so far.
If $A$ is ...
1
vote
1answer
46 views
Two languages such that their Kleene closures are equal
I am trying to solve the following problem:
Find languages S and T over the alphabet $\{a, b\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$,...
1
vote
1answer
744 views
Is it true that if L* is recursive, L is also recursive?
Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive?
I know that the opposite direction is true:
If $L$ is recursive, then $L^*$ is recursive.
But I don't know how ...
-1
votes
1answer
37 views
Can an infinite regular language be decomposed in this way?
If $A$ is an infinite regular language, can there exist a finite regular language $B$ such that $A = BB^*$?
0
votes
1answer
218 views
What does {a,b}* for DFA's mean?
For instance when the question contains $\{a,b\}^*$ does this mean that the DFA must have at least one $a$ and one $b$ on top of whatever conditions it has?
For example a DFA that accepts $\{w \in \{a,...
0
votes
2answers
89 views
Kleene star operations
Let $šŗ$ be any alphabet and let $š³_š \subseteq šŗ^{ā}$ and $š³_2 \subseteq šŗ^{ā}$ be two non-empty languages.
a. If $š³_š šŗ^{ā} \neq šŗ^{ā}$ than what can we say about $L_1$.
b.Let $\Lambda \...
2
votes
2answers
71 views
Prove, that $A^+\subseteq A^*$ where $A$ is a formal language
Prove, that $A^+\subseteq A^*$, where $A$ is a formal language.
The definition of $A^+$ is $\bigcup_{i\in\mathbb{N}\setminus \{0\}}A^i$, which would be $A^1 \cup A^2 \cup \dots \cup A^i$. Likewise, $...
0
votes
1answer
126 views
Is the Kleene star of an intersection always equal to the intersection of kleene stars?
I know that the Kleene star of an intersection is contained in the intersection of Kleene stars, but are they necessarily equal?
For example, given two formal languages, $A$ and $B$, I know that $(A\...
0
votes
1answer
103 views
Lexicographic Order of Expression [Automata Theory]
what will be kleene star "expansion" of expression $a^*b^*$ in lexicographic order?
I'm confused and I really want to clear my concepts so I can proceed further
1
vote
1answer
133 views
Kleene Star regex question, sed behavior? [closed]
Kleene Star with 'sed' is behaving as expected for me, with exception of a case where the input pattern is "ab" and the regex is "b*". Does anyone know why this regex is not being matched against the ...
1
vote
1answer
947 views
Meaning of L* if L is a language
I can't find anywhere the meaning of $L^*$, given that $L$ is a language. I know $^* $ means repetition, for example $0^*$ = $\{ \epsilon, 0, 00, 000, \dots \}$. Or if $A$ is an alphabet $A^*$ are all ...
5
votes
1answer
204 views
Is a kind of reverse Kleene star of a context-free language context-free?
Recently I had a question on one of my assignments asking to prove or disprove the following:
Let $L$ be a language. If $L^*$ is context-free then $L$ is context-free.
Now obviously this is false ...
1
vote
2answers
134 views
DFA & RE from descriptive definition of given regular language
I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.
Some strings ...
1
vote
2answers
3k views
DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)?
Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we ...
0
votes
1answer
39 views
Proving $A^\ast = A$ on a given set
I am working on some set theory and am trying to prove how a set can have the property $A^* = A$.
For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I ...
3
votes
1answer
142 views
How is $L^* - \{\epsilon \} \neq L^+$?
I was asked which among the following is true:
$\Sigma^*-\{\epsilon\} = \Sigma^+$
$L^* - \{\epsilon \} = L^+$
As I can see, both $\Sigma^*$ & $L^*$ are sets. I thought both were true ...
1
vote
1answer
89 views
Find the number of strings in the language $(ā ā ^ā + ā )$
Consider the language $L = \emptyset\emptyset^ā + \emptyset$.
How many words does $L$ contain? Zero or one?
Note: $\emptyset^ā =\{\epsilon\}$.
1
vote
1answer
147 views
Inductive approach on Kleene star proof
I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$
I could be on the wrong track here, but I figured an inductive approach is a good ...
2
votes
1answer
84 views
How to Apply Elementary Axioms from Kleene Star to an Inequality
Axioms For *
\begin{align}
1 + aa^* &\leq a^* \\
1 + a^*a &\leq a^* \\
b + ax &\leq x \to a^*b \leq x \\
b + xa &\leq x \to ba^* \leq x \\
\end{align}
Elementary Results
\begin{...
2
votes
1answer
72 views
Does the set $\{10^n \mid n\geq1\}^*$ include $10100$?
Consider the following set constructed with a regular Kleene-star operation:
$$
\{10^n \mid n\geq1\}^*
$$
Would something like $10100$ be in this set? I know $1010,100100100,1000,$ etc would be, but ...
1
vote
1answer
279 views
Nondeterministic PDA for the following language with Kleene star
I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:
$$L = (aaa^*bab)$$
My normal approach to ...
0
votes
1answer
1k views
Does adding S->SS in a context-free grammar change the language to its Kleene star?
Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^*$, why? What about grammars in Chomsky ...
2
votes
3answers
109 views
When is the empty word part of $A^+$?
My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case.
Given is A, a subset of {0,1}$^*$.
...
0
votes
0answers
18 views
Validity of some Kleene star statements [duplicate]
I'm taking an intro to computability course right now and I'm having some trouble with a couple examples that the professor doesn't seem too clear on.
We're learning about languages and doing some ...
2
votes
1answer
819 views
Prove that $L$ is closed under Kleene star iff $L=NL$
Prove that $L$ is closed under Kleene star iff $L=NL$
Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$. Lets consider ...
3
votes
1answer
143 views
Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$
Let $L=\{a^nb^n | n \ge 1\}$, then $L^\star=L^0 \cup L^1 \cup L^2 \cup L^3 \cup \dots = \{\epsilon\} \cup \{a^nb^n\} \cup L^2 \cup L^3 \cup \cdots$ .
How to find $L^2$ and $L^3$, and is $L^2=\{a^nb^...
2
votes
1answer
233 views
Kleene star Empty language
I had a test a couple of days ago and one of the question had 2 statements :
$L^+ = L^\ast$
$L$ contains $\varepsilon$
I had to say does 1 imply 2, does 2 imply 1 or do they both imply each other.
...
1
vote
2answers
626 views
To which character or characters does a Kleene star apply?
If you have a Kleene star applying to a set of characters not in any closure, does it apply to that whole string, or just the one character it belongs to? Any examples I search don't specify.
For ...
1
vote
0answers
1k views
What is the best way to prove (S+)+ = S+? [closed]
Lets say I have the below language:
S = {a, b}
So if we apply Kleene plus to that language, it is something like:
...
0
votes
0answers
118 views
Why is DCFL not closed under kleene star? [duplicate]
I honestly haven't an idea how to proof that eventhough I can understand the background, could someone help me?
0
votes
1answer
470 views
Reflexive transitive closure = (zero or more) Kleene star?
In Alloy Tutorial they denote some reflexive transitive closure with Kleene star saying that they admit zero or more elements at that position.
...
-2
votes
1answer
378 views
Kleene star of L
$L^*$ is the kleene star of L.
say we have a def: $L^*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$
then prove that: $L^*$ = $L$ if and only if $L$ = $L$ o $L$
how do i prove this?
1
vote
2answers
3k views
Proving $(a+b)^* = b^*(ab^*)^*$ equationally
I am new to automata theory and have a problem in understanding equivalence of regular expressions, though I can go for the construction procedure of minimized DFAs to prove that both are equal.
I ...
7
votes
3answers
1k views
Will $L = \{a^* b^*\}$ be classified as a regular language?
Will $L = \{a^* b^*\}$ be classified as a regular language?
I am confused because I know that $L = \{a^n b^n\}$ is not regular. What difference does the kleene star make?
2
votes
1answer
669 views
Is the Kleene star of an intersection contained in the intersection of Kleene stars?
I need to find if given two formal languages $L_1$ and $L_2$ $$(L_1 \cap L_2)^*\subseteq (L_1^* \cap L_2^*) $$
I think that it's true since this can be rewritten as $$ \bigcup^\infty_{i=0}(L_1 \cap ...
12
votes
3answers
2k views
Regular languages that can't be expressed with only 2 regex operations
I thought all regular languages could be expressed with regular expressions (if a language is regular, it can be expressed with regex), but
I have been told that you need all three of the regular ...
3
votes
4answers
599 views
How to determine if a regular language L* exists
I'm trying to make sense of regular languages, operations on them, and Kleene operations.
Let's say I define a language with the alphabet {x, y}. Let's further say that I place the restriction that ...
1
vote
1answer
521 views
Kleene star differences
We have languages $A= \{a\}$ and $B = \{b\}$. If we consider $(A\cup B)^*$, where ${}^*$ means Kleene star, we have a set of words like $\{\lambda, a,b,aa,ab,aaa,\dots\}$, where $\lambda$ is the empty ...
15
votes
2answers
5k views
Kleene star operation on the empty language
In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language.
However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.
I am not ...
-3
votes
1answer
481 views
Is the set of all strings over a finite alphabet finite? [closed]
Suppose $Ī£=\{0,1\}$; then $Ī£^*$ is the set of all strings over $Ī£$.
Is $Ī£^*$ over $Ī£$ finte?
