1
vote
1answer
279 views

induction proof for kleene star

i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of trouble with converting general ideas into formal mathematical proofs. the question ...
1
vote
2answers
36 views

Prove by induction on a string

I want to practice proving the following: Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same. For ...
0
votes
1answer
45 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
0
votes
2answers
131 views

Help with regular expression subset proof

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other. The expression is: $(A^*B^*)^* \subset ...