Questions tagged [kleene-star]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
38 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.
user avatar
4 votes
0 answers
134 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 ...
user avatar
  • 41
0 votes
1 answer
70 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 ...
user avatar
1 vote
1 answer
35 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 ...
user avatar
  • 1
0 votes
0 answers
41 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 ...
user avatar
2 votes
1 answer
109 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 ...
user avatar
0 votes
1 answer
70 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)$?
user avatar
  • 11
3 votes
1 answer
167 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 ...
user avatar
  • 33
1 vote
1 answer
69 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 ...
user avatar
1 vote
2 answers
293 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 ...
user avatar
  • 13
1 vote
1 answer
58 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$,...
user avatar
1 vote
1 answer
827 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 ...
user avatar
-1 votes
1 answer
40 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^*$?
user avatar
  • 1
0 votes
1 answer
946 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,...
user avatar
0 votes
2 answers
115 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 \...
user avatar
2 votes
2 answers
80 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, $...
user avatar
0 votes
1 answer
198 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\...
user avatar
0 votes
1 answer
323 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
user avatar
  • 17
1 vote
1 answer
203 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 ...
user avatar
  • 175
1 vote
1 answer
2k 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 ...
user avatar
  • 13
5 votes
2 answers
281 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 ...
user avatar
1 vote
2 answers
150 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 ...
user avatar
1 vote
2 answers
5k 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 ...
user avatar
0 votes
1 answer
40 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 ...
user avatar
  • 11
3 votes
1 answer
179 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 ...
user avatar
  • 1,243
1 vote
1 answer
105 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\}$.
user avatar
1 vote
1 answer
214 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 ...
user avatar
2 votes
1 answer
113 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{...
user avatar
2 votes
1 answer
75 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 ...
user avatar
1 vote
1 answer
383 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 ...
user avatar
  • 560
0 votes
1 answer
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 ...
user avatar
2 votes
3 answers
124 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}$^*$. ...
user avatar
  • 23
0 votes
0 answers
19 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 ...
user avatar
2 votes
1 answer
967 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 ...
user avatar
3 votes
1 answer
148 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^...
user avatar
2 votes
1 answer
262 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. ...
user avatar
1 vote
2 answers
774 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 ...
user avatar
  • 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: ...
user avatar
  • 11
0 votes
0 answers
124 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?
user avatar
  • 1
0 votes
1 answer
577 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. ...
user avatar
-2 votes
1 answer
477 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?
user avatar
1 vote
2 answers
4k 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 ...
user avatar
  • 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?
user avatar
2 votes
1 answer
791 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
2 votes
1 answer
592 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 ...
user avatar
  • 43
17 votes
2 answers
6k 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 ...
user avatar
  • 864
-3 votes
1 answer
795 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?
user avatar
-1 votes
1 answer
79 views

Prove the language of all concatenations of words in a regular language is regular [duplicate]

For a language $L\in\Sigma^*$ we define $$ L^*=\{w\mid \exists k\in \mathbb{N}\cup\{0\}, ∃x_1,...,x_k\in L \ (w=x_1...x_k) \} $$ Let $L$ be a regular language over some alphabet $\Sigma$. Prove that $...
user avatar