1

Consider the alphabet {a, b}. Also consider the following two languages:

  • Let L1 be the smallest set such that

    Basis: The empty string A is in L1.

    Induction: For every xL1, both ax and axb are in L1.

  • L2 = {ai bj|i ≥ j}

Prove that L1 = L2 as follows:

a) Prove by structural induction that L1 ⊆ L2.

b) Prove by complete induction that L2 ⊆ L1.

NOTE: State clearly what is your Induction Hypothesis (IH) as well as the step in your proof where the (IH) is being used.

I need help with the above question I don't understand what I am asked to do can any one explain it to me and hint's will be appreciated thank you

1 Answers1

1

HINTS:

Since you say that you don't understand what you're asked to do, I'll try and give a vague outline to get you started before spoiling everything.

For part a, show that any string in $L_2$ must follow the rules defining $L_1$ - start by showing that $L_2$ contains the empty string, then show that a word in $L_2$ extended according to these rules must also be in $L_2$. Since $L_1$ is the smallest set whose elements satisfy these rules, you will have shown that $L_1 \subseteq L_2$.

For part b, do the same trick in reverse. Show that every string constructed by the rules of $L_1$ must be of the form $a^ib^j$ for $i \geqslant j$. Construct the base case, the simplest possible version of what you're trying to show. For the inductive step, assume that what you're trying to show must be true for every $i+j < k$ for your inductive hypothesis, and use that fact to show that it must also be true for $i+j = k$.

Read over this a few times before heading on the the spoiler.

SPOILER:

Let $\varepsilon$ be the empty string. Let $i = j = 0$. Clearly, $i \geqslant j$, so $a^0b^0 \in L_2$, so $\varepsilon \in L_1 \cap L_2$.

Let $x = a^ib^j \in L_2$ for some $i \geqslant j$. Since $x \in L_1$, extending $x$ by either "Induction" rule must give another element in $L_1$. Since $x = a^ib^j$, $ax = a^{i+1}b^j$. Since $i \geqslant j$, it must be the case that $i+1 \geqslant j$. Similarly, $axb = a^{i+1}b^{j+1}$, and $i+1 \geqslant j+1$, so for any $x \in L_2$, both $ax \in L_2$ and $axb \in L_2$.

All elements in $L_2$ satisfy the rules of $L_1$. Since $L_1$ is the smallest set whose elements satisfy these rules, it must be the case that $L_1 \subseteq L_2$

This solves part a.

We know that $\varepsilon \in L_1 \cap L_2$. We will suppose that

$$ \forall x \in L_2 \quad |x|<n \implies x \in L_1 \quad \quad \mbox{(IH)} $$

This is clearly true for $n=1$. We will assume that (IH) is true for all $n \in \{1, 2, ..., k-1\}$, and show that it must then be true for $n = k$.

Let $x \in L_2$ such that $|x| = k>1$. Then $x = a^ib^j$ for $i+j=k$, $i \geqslant j$.

Suppose $i=j$. Then $i-1 \geqslant j-1$, so $a^{i-1}b^{j-1}\in L_2$, but $|a^{i-1}b^{j-1}| < k$, so it must also be the case that $a^{i-1}b^{j-1} \in L_1$ from (IH).

Suppose $i>j$. Then $i-1 \geqslant j$, and the same argument as above holds.

So if (IH) is true for $n \in \{1,2,...,k-1\}$, (IH) must also be true for $n=k$, so (IH) is true for any finite-length string in $L_2$. Since all strings in $L_2$ are finite length, it must be true for all of $L_2$

So $L_2 \subseteq L_1$

This solves part b.

These proofs seem a little long-winded, and perhaps they are. You could probably get away with a far more terse answer, but I've tried to answer as precisely as possible.

ymbirtt
  • 1,221