4 ms·
In that case it’s absolutely incorrect, not merely misleading. It definitely should not be between FSM and CFG. It should either be equal to FSM (regular expres
by klodolph 7y ago
In that case it’s absolutely incorrect, not merely misleading. It definitely should not be between FSM and CFG. It should either be equal to FSM (regular expressions) or it should be much more powerful (if you have backreferences, like PCRE does, you can encode SAT problems in your regexes, and this cannot be done with CFG, but recursive languages are strictly more powerful).
- AlchemistCamp 7y ago> It should either be equal to FSM... superset != strict superset
- klodolph 7y agoThat's why I originally said “misleading”, if we’re going to be pedantic.