Prove that L is a sub-language of the CFG G by using induction. (CFG,Induction,School)

Question

i am asking for help with a question from a course in Logic im reading at university. I am aware that this type of question is frequently asked here(i have looked at alot of other questions/answers) but i think it would be very helpful if i had some tips specific for my problem.

The question is:

Consider the following grammar: S → SS | aSb | ϵ

Prove that the following language is one of its sub-languages. Use induction. $${a^nb^n | n ≥ 0}$$

Im very new to induction and cannot figure out where to begin. Ofcourse you can immediately see that as long as you select the production "aSb", any amount of times, then end with an epsilon, you will indeed get $a^nb^n$. But if you select the production "SS" you will no longer get that language.

So i want to know how to deal with that it asks for a sub-language instead of the full language, and also i would like to know how to use induction make this proof.

I realize that i am pretty much asking for the entire answer here but if you can give me some help without giving away the full answer that would be very helpful.

Thanks

Edit: Thank you for all the help so far. If i use it i come up with something like:

Induction over n: Proving that n=1 generates string "ab".

Do i prove this by this line: $S->aSb->aϵb->ab$

Or by this: $a^1b^1 = ab$ ?

Moving on; Inductive assumption: This holds for n=k.

$a^kb^k$

Now, prove that this holds for k+1.

$a^{k+1}b^{k+1} = a^ka^1b^kb^1$

I now ask for feedback on my attempt. Thanks again.

Answer 1

Your problem is not with this topic but with your understanding of logic and induction. First let me point out what's wrong with your attempt.

Errors

Let $G$ be the given CFG.

n=1 generates string "ab"

This is unfortunately meaningless. What does "generate" mean? How can "$n=1$" do anything? If you want to say "$a^1 b^1$ is generated by $G$", say so. Don't say anything else.

S−>aSb−>aϵb−>ab

This line is true for $G$. You could say "$a^1 b^1$ is generated by $G$, via S−>aSb−>aϵb−>ab".

Inductive assumption: This holds for $n=k$.

$a^k b^k$.

$a^k b^k$ is just a string, not a sentence! Just like you can't say "This holds for $n = k$: Elephant!", so also what you wrote is simply meaningless and has no truth value.

Now, prove that this holds for $k+1$.

Not sure what you're talking about here. Are you referring to proving the following line?

$a^{k+1} b^{k+1} = a^k a^1 b^k b^1$.

If so, then this has nothing to do with induction, because this very line is always true regardless of $k$.

Correct structure

Now here is the correct proof structure.

Let $G$ be the given CFG.

Let $P(n)$ be equivalent to "$G$ generates $a^n b^n$", for each $n \in \mathbb{N}$.

$G$ generates $a^0 b^0$ via $S \to ε = a^0 b^0$.

Thus $P(0)$ is true.

For any $n \in \mathbb{N}$ such that $P(n)$ is true:

  $G$ generates $a^n b^n$.

  Thus $S \to^* a^n b^n$.

  $G$ generates $a^{n+1} b^{n+1}$ via $S \to \cdots \to a^{n+1} b^{n+1}$.

  Thus $P(n+1)$ is true.

Therefore by induction $P(n)$ is true for every $n \in \mathbb{N}$.

Therefore $G$ generates $a^n b^n$ for every $n \in \mathbb{N}$.

Your task is now to fill in the blanks where I put "$\cdots$". You have to figure out how to use the previous line in order to get from starting symbol $S$ to $a^{n+1} b^{n+1}$. This should be easy. Write your solution in a comment and I'll check it.

Answer 2

1. Given languages $L, L'$, we say $L'$ is a sublanguage of $L$ if $L' \subseteq L$. That is, if all words of $L'$ are also words of $L$.
2. For the language $\{a^nb^n\mid n\ge0\}$, the obvious variable to induct over is $n$. We can use induction to prove that $a^nb^n$ is in the given CFG for all $n$.

---

In general, it is often beneficial to prove things about languages using structural induction: the principle that if the results of all rules of formation of the language fulfil a certain condition if all inputs do.

For example, taking $S \to SS\mid aSb\mid \epsilon$, we can prove using structural induction the statement: an expression resulting from these rules contains no other symbols but the metasymbol $S$ and $a,b$.

The proof then proceeds by checking that starting with $S$ (for which the premise holds true), the rules of formation preserve the truth of this statement.