Questions tagged [kleene-star]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
15
votes
2answers
3k 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 ...
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 ...
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?
5
votes
1answer
142 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 ...
3
votes
4answers
209 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 ...
3
votes
1answer
131 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^...
3
votes
1answer
46 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 ...
2
votes
1answer
70 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 ...
2
votes
1answer
165 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. ...
2
votes
1answer
495 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 ...
2
votes
3answers
86 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}$^*$. ...
2
votes
1answer
482 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 ...
2
votes
2answers
506 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 ...
2
votes
1answer
56 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{...
1
vote
2answers
64 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
380 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
1answer
81 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 ...
1
vote
1answer
60 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
139 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 ...
1
vote
1answer
422 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 ...
1
vote
1answer
38 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
72 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 ...
1
vote
0answers
352 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
1answer
352 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 ...
0
votes
1answer
60 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
2answers
1k 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 ...
0
votes
1answer
36 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 ...
0
votes
1answer
18 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
0
votes
1answer
246 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. ...
0
votes
0answers
10 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 ...
0
votes
0answers
101 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?
-2
votes
1answer
276 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?
-3
votes
1answer
178 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?