What's the deal with Deno? We talk with a major contributor to find out. Listen now.

# Questions tagged [kleene-star]

The tag has no usage guidance.

40 questions
Filter by
Sorted by
Tagged with
35 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 ...
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$,...
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 ...
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^*$?
93 views

70 views

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
108 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 ...
610 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 ...
187 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 ...
128 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 ...
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 ...
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 ...
102 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 ...
83 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\}$.
114 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 ...
67 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{...
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 ...
231 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 ...
767 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 ...
99 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}$^*$. ...
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 ...
### 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 ...