Questions tagged [kleene-star]
The kleene-star tag has no usage guidance.
39
questions
1
vote
1answer
44 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
698 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
33 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
86 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
72 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
70 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
110 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
47 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
104 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
588 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
177 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
126 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 ...
2
votes
2answers
2k 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
97 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
81 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
113 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
66 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
71 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
227 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
762 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
97 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
16 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
757 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
139 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
213 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
534 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
695 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
116 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
385 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
339 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
2k 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
605 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
334 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
481 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
4k 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
334 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?
