Skip to main content

New answers tagged

4 votes
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$ ...
codeR's user avatar
  • 1,281
3 votes

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.
gnasher729's user avatar
  • 30.5k
2 votes

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 ...
Knogger's user avatar
  • 1,202
2 votes

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 ...
D.W.'s user avatar
  • 161k
0 votes

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.
Hendrik Jan's user avatar
  • 30.8k
2 votes

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 ...
chi's user avatar
  • 14.6k
4 votes

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 ...
Nathaniel's user avatar
  • 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 ...
Knogger's user avatar
  • 1,202
0 votes

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

Every regular expression have an automata recognising it and the same holds for the converse too. Link to a previous post. Regular languages are defined as the language that can be recognized by a ...
0 votes

How to simplify this regular expression?

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$...
Nikos M.'s user avatar
  • 979

Top 50 recent answers are included