Extra Theory of Computing

What cannot be recognized by any finite automata?

Answer explanation

Non-regular languages have structures that require more memory than finite automata can provide.

What mathematical method is used to prove a language is non-regular?

In a grammar, what is the name for substitution rules?

What recursive method is more powerful than regular expressions or automata for describing a language?

The label "0->Ɛ" would do what to the stack?

What is the term for replacing strings with variables?

What is the substring to be replaced by a non-terminal in the next step called?

What has equal power to a deterministic pushdown automata?

what grammar is used to get around strictness?

What technique is used to get around strictness?