Questions tagged [kleene-star]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
2answers
62 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
71 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
27 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
48 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
125 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
150 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
83 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
943 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
37 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
58 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 ...
-3
votes
1answer
207 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?
1
vote
1answer
64 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
79 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
60 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
1answer
167 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 ...
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 ...
0
votes
1answer
511 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
89 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
11 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
502 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
133 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
173 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. ...
0
votes
1answer
279 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. ...
1
vote
2answers
410 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
435 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
105 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
286 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?
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 ...
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
516 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
222 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
430 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
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 ...