# Questions tagged [kleene-star]

The tag has no usage guidance.

31 questions
Filter by
Sorted by
Tagged with
27 views

### Kleene Star regex question, sed behavior? [on hold]

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 ...
50 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 ...
125 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 ...
50 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 ...
144 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 ...
35 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 ...
39 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 ...
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\}$.
61 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 ...
48 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{...
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 ...
130 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 ...
261 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 ...
80 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}$^*$. ...
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 ...
### 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 ...