Exercise Related to CFG

Exercise Related to CFG

by MUHAMMAD ALI -
Number of replies: 1

Hi,

I would like to ask If we write a following context-free grammar (CFG) for language L1, would that be sufficient to demonstrate that L1 is a context-free language (CFL), or is designing a deterministic finite automaton (DFA) the only correct approach?


     S → AB

    A → aAb | ε

    B → Bb | ε



.


In reply to MUHAMMAD ALI

Re: Exercise Related to CFG

by Giorgio Satta -

Muhammad: L1 is in CFL - REG. Therefore you need first to show it is not in REG by p lemma, second you need to provide a CFG or PDA; I recommend the second. The CFG you provide for L1 is not correct ... it generates only a subset of the strings in L1.