JavaEar 专注于收集分享传播有价值的技术资料


  1. Only regular languages can be converted to a DFA, and not all CFGs represent regular languages, including the one in the question.

    So the answer is "no".

    NFAs are not more expressive than DFAs, so the above statement would still be true if you replaced DFA with NFA

    A CFG represents a regular language if it is right- or left-linear. But the mere fact that a CFG is not left- or right-linear proves nothing. For example, S→a | a S a happens to generate the same language as S→a | S a a.