0
$\begingroup$

I just started studying the concept of context-free grammars and I find something very confusing. Watching a video I found someone tackling the problem ${0^n 1^m : n,m\geq 0}$.

I thought that the simple answer would have the production rules: $S \rightarrow \epsilon \ | \ 0S \ | \ S1$

Since I thought this implies that whichever string you have, you can always place a $0$ in front of the string or a $1$ at the end of the string. However it seems that you can also create the string $0101$ with these production rules, could someone explain to me why my production rules won't give the desired outcome?

$\endgroup$
6
  • $\begingroup$ How exactly do you produce 0101? Show me. $\endgroup$
    – gnasher729
    Dec 4, 2023 at 13:23
  • $\begingroup$ @gnasher729 That's the problem, I don't exactly get it but this is what I found on the internet. S -> 0S -> 0S1 -> 01S1 -> 010S1 -> 0101. What's bugging me is the step from 0S1 to 01S1, since there is no step from S to 1S $\endgroup$
    – Jellyfish
    Dec 4, 2023 at 13:26
  • $\begingroup$ The longer I think about it, the more the derivation to 0101 seems incorrect. Could my answer be correct? $\endgroup$
    – Jellyfish
    Dec 4, 2023 at 13:33
  • $\begingroup$ Looks like you asked ChatGPT. That step is absolute nonsense. There is no way to get to 0101. Yes, your answer was correct. $\endgroup$
    – gnasher729
    Dec 4, 2023 at 13:34
  • $\begingroup$ @gnasher729 it's weird that in the youtube video from "Easy Theory" he uses a different approach which is overcomplicating the problem. He solves it with: S -> 0S | P P -> 1P | \epsilon. But thanks! $\endgroup$
    – Jellyfish
    Dec 4, 2023 at 13:36

1 Answer 1

0
$\begingroup$

You can't produce $0101$ because every time you use $0S$ you are putting a $0$ at the beginning of the string. Whenever you want to insert a $1$, it directly goes to the end of the string and it will remain the last element of the string. This holds also in the opposite way. You can add $1$s and, if you add a $0$, it became the first element of the string and you can only add characters to the right of this $0$.

The proposed production rules are correct and it can be easily shown by induction on the number of times a production rule is applied $ \ell$.

The strings obtained by the production rules (starting from empty string) $S\rightarrow \epsilon \ | \ 0S \ | \ S1 $ are in the form $0^n1^m$.

a) Base case: $\ell=0$ this is true because $S=\epsilon = 0^0 1^0$.

b) Inductive step: Assuming the thesis true for $\ell$ applications of the production rules, we show it for $\ell +1$ applications. Assume $S$ is the results of $\ell$ applications of the production rules, thus, by inductive hypothesis $S=0^n1^m$. Now, we have three possibilities, one for each production rule:

  1. $S\rightarrow \epsilon$, in this case the thesis remains true.
  2. $S\rightarrow 0S$, then we added a starting $0$, so if by inductive hypotesis $S=0^n1^m$, we obtained $0^{n+1}1^m$.
  3. $S\rightarrow S1$, as previous case, we obtain $0^n 1^{m+1}$.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.