Questions tagged [kleene-star]
The kleene-star tag has no usage guidance.
54
questions
1
vote
1
answer
37
views
Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.
The wikipedia article states:
Another way to state Schützenberger's theorem is that star-free languages and ...
- 67
1
vote
1
answer
78
views
Is (a*b) or (a*b)* star-free?
Here is the proof of a∗ being star-free:
$\Sigma* = \bar{\emptyset} $
$ A∗= \overline{Σ∗(Σ∖A)Σ∗} $
Would this be a proof for $a * b$? :
$ A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)} $
For $(A * B )*$ it seems more ...
- 67
0
votes
1
answer
30
views
Languages: Prove or Disprove that $A^* = B^* \rightarrow A=B$
A colleague and I with pretty low-grade practical backgrounds decided it's time to try learning theory. This question is asked in a slide-deck he tracked down somewhere or another online without an ...
- 1
0
votes
0
answers
49
views
Why does "NP is closed under Kleene star" proof reject correct word? [duplicate]
Show that P and NP are closed under Kleene star. I found possible solutions to these problems, more specifically:
P - finding all subwords from a giving word and looking if there is a connection ...
- 1
0
votes
0
answers
352
views
Are regular expression a* and a.a* equal?
a* = {λ, a, aa, aaa, aaaa.....}
a.a* = a.{λ, a, aa, aaa, aaaa.....} = {a, aa, aaa, aaaa, aaaaa....}
Then these two regular expressions above should not be equivalent. Please correct me if i am wrong.
4
votes
0
answers
151
views
Regular languages for which star height is not increased by complementation
The set of (non-generalized) regular expressions over an alphabet $\Sigma$ is the set of expressions generated by the following grammar, where $a\in \Sigma$ ranges over symbols in the alphabet:
$$
\pi ...
- 41
0
votes
1
answer
254
views
Simplifying regular expression
I'm having trouble understanding the simplification of the following regular expression
\begin{align}
R = ε | 1 | (ε | 1)(ε | 1)^*(ε | 1) = 1^*
\end{align}
In my lectures only the simplified solution ...
- 11
3
votes
2
answers
66
views
How to show closure of regular languages without DFA,NFA,reg expressions
Given a $\Sigma$ I define a regular language as one of the folllows:
$\emptyset$
$\left\{ \sigma \right\}$ for any $\sigma \in \Sigma$
$L_1 \cup L_2$ for regular $L_1, L_2$
$L_1 \cdot L_2 $ for ...
- 435
-1
votes
2
answers
79
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 ...
2
votes
1
answer
117
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 ...
user129648
0
votes
1
answer
116
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)$?
- 11
3
votes
1
answer
213
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 ...
- 33
1
vote
1
answer
87
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 ...
- 25
1
vote
2
answers
438
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 ...
- 113
1
vote
1
answer
125
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$,...
user115951
1
vote
1
answer
1k
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
1
answer
49
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^*$?
- 1
0
votes
1
answer
2k
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
2
answers
124
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
2
answers
109
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, $...
- 156
0
votes
1
answer
266
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\...
- 11
0
votes
1
answer
525
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
- 13
1
vote
1
answer
295
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 ...
- 175
1
vote
1
answer
3k
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 ...
- 13
5
votes
2
answers
318
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
2
answers
210
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
2
answers
7k
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
1
answer
41
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 ...
- 11
3
votes
1
answer
198
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,293
1
vote
1
answer
137
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\}$.
- 13
1
vote
1
answer
259
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 ...
- 131
2
votes
2
answers
140
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{...
- 37
2
votes
1
answer
76
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
1
answer
480
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 ...
- 570
0
votes
1
answer
2k
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
3
answers
141
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}$^*$.
...
- 23
0
votes
0
answers
20
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
1
answer
1k
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 ...
- 379
3
votes
1
answer
150
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^...
- 33
2
votes
1
answer
290
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.
...
- 123
1
vote
2
answers
954
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 ...
- 135
1
vote
0
answers
2k
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:
...
- 11
0
votes
0
answers
128
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
1
answer
667
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
1
answer
541
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
2
answers
5k
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 ...
- 213
7
votes
3
answers
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?
- 91
2
votes
1
answer
923
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 ...
- 21
12
votes
3
answers
3k
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 ...
- 383
3
votes
4
answers
1k
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 ...
- 61