1,279 views

1 Answer

Best answer
4 votes
4 votes
The condition to be checked here is no. of b's following a's should be more than the no. of a's but less than twice the no. of b's. This cannot be done using a DPDA. But for each a we can non-deterministically guess that it can generate either one b or two bs and this way we can make a PDA. The context-free grammar would be

$$S \to aSb \mid aSbb \mid \epsilon$$

Related questions

1 votes
1 votes
3 answers
1
Shefali asked Oct 24, 2015
738 views
$L=\left\{ w\in(a+b)^* \mid w \\ \text{ has at least as many occurrences of (bba)'s as (abb)'s}\right\}$    Identify the class of the language.