# Tag Info

Accepted

### Why $(a+b)^* = (a^*b)^* a^*$

Consider any string $\omega$ that belongs to $(a+b)^*$. Now suppose $\omega$ contains $n$ number of $b$s. We can now partition $\omega = x_1 x_2 \dots x_n y$, where all $x_i$ are of the form $a^*b$ ...
• 1,281

### Why $(a+b)^* = (a^*b)^* a^*$

Every b in a string belonging to (a+b)* is preceded by 0, 1, 2 or more a's. And the last be is followed by 0, 1, 2 or more a's.
• 30.5k

### How to formally prove that any regular expression can be written as a finite combination of base cases and operations?

What you have there is a recursive definition. Every regular expression is generated by a finite number of applications of rules 1.-6., so you can simply do mathematical induction over the number of ...
• 1,202

### Kleene star of any unary language is regular

That is not what the last paragraph says. The last paragraph says "we know that we can get any word whose length is multiple of $m$ if ..". In the example, $m=2$, so you should not expect ...
• 161k

### How to demonstrate that the intersection of a context-free and a regular language is context-free?

There is one special case you must deal with. The PDA might be able to perform a $\varepsilon$-transition where the FSA can't.
• 30.8k

### Number of a, b and c is even

For all $i,j,k \in \{0,1\}$ create a non terminal $A_{ijk}$ for the language of strings where $i,j,k$ are the parity of the number of $a,b,c$, respectively. You can then easily connect these non ...
• 14.6k

### Number of a, b and c is even

Using a finite automaton, it is quite easy to construct a regular grammar for the same language. Given $A = (Q, \Sigma, \delta, q_0, F)$ a complete DFA, consider $G = (\Sigma, V, P, S)$ the grammar ...
• 15.8k
1 vote
Accepted

### Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma

This isn't how the Pumping Lemma works. The Lemma states that "if $L$ is regular then for all $w \in L$ there exists factors $w = xyz$ satisfying ...", not "if $L$ is regular then for ...
• 1,202
### Help regarding a proof in which i am able to prove a regular language $(a(a+b)*)$ as irregular using pumping lemma
My three cents. Unless I am missing something in the notation, a typical (random) string, ie $$a^{k_1}b^{k_2}a^{k_3} \dots b^{k_{n-1}}a^{k_n}$$ with $n$ terms and $k_i \ge 0$ arbitrary ($1 \le i \le n$...