0

How does one know which string to choose when nothing is given in the question?

Paritosh Potukuchi
  • 1

2 Answers2

1

HINT: You can use $abaa$. Try it yourself; if you get stuck, I’ve left two leftmost derivations in the spoiler-protected block below.

$S\Rightarrow Sa\Rightarrow SbSa\Rightarrow abSa\Rightarrow abaa$ and $S\Rightarrow SbS\Rightarrow abS\Rightarrow abSa\Rightarrow abaa$

Brian M. Scott
  • 616,228
  • I would like to know how you guessed the string abaa ? – Paritosh Potukuchi Oct 28 '16 at 17:00
  • @Paritosh: I began with the idea that starting with $S\to Sa$ and following that with one of the last three productions would yield a $4$-character string ending in $a$. Alternatively, if I began with $S\to bSS$ or $S\to SbS$, I could eventually use $S\to Sa$ to get a $4$-character string ending in $a$. Then it was just a matter of picking the right productions of the form $S\to xxx$ to end up with the same string. – Brian M. Scott Oct 28 '16 at 17:14
0

I generally start by looking for a single production with repeated nonterminals that easily generate the same sequence twice. In your case I 'hit jackpot' with the last: S -> SbS. This generates the sequence SbSbS two ways: (SbS)bS and Sb(SbS). I don't think the same thing happens with S->bSS or S->SSb.

Failing that, I would try to combine two or more productions to achieve the same effect. This works with the productions S->bSS and S->SSb, which combine to produce the string bSSSb two ways: (bSS)Sb or bS(SSb).

Failing that, look for ways to produce the same terminal(s) at different heights of the parse tree. That leads to the approach implied by @Brian M. Scott.

PMar
  • 1