1. How to prove a language is CFL?
-
Write its context free grammar.
-
Design a push down automata for the language.
-
Apply closure properties.
2. How to prove a language is non-CFL?
•Use pumping theorem to prove it is not context free.
•Apply closure properties.
3. Classes of Languages
- Recursive = decidable: their Turing machine always halt
- Recursively Enumerable (RE) but not recursive: their Turing machine halt if they accept
- Non recursively enumerable (non-RE): there are not Turing machine for them.
Equivalence Relation
ReplyDeleteLet A be a set and ~ be a binary relation on A. ~ is called an equivalence relation if and only if for all , all the following holds true:
Reflexivity: a ~ a
Symmetry: if a ~ b then b ~ a
Transitivity: if a ~ b and b ~ c then a ~ c.
The equivalence class of a under ~, denoted [a], is defined as . A together with ~ is called a setoid.
http://en.wikipedia.org/wiki/Equivalence_relation
Universal Instantiation
ReplyDeleteUI can be applied many times to add new sentences. The new KB is equivalent to the old one.
Existential Instantiation
EI can be applied only once. The new KB is not equivalent to the old one. But they are equivalent in the degree of satisfiable.
FOL: Conversion to CNF
ReplyDelete1.Eliminate biconditionals and implications;
2.Move negation inward;
3.Standardize variables: each quantifier should use a different one;
4.Skolemize: a more general form of existential instantiation: Each existential variable is replaced by a Skolem function of the enclosing universally quantified variables;
5.Drop universal quantifier;
6.Distribute and over or.
How to prove a language is regular ?
ReplyDeleteDesign FA for the language.
Design regular expressions for the language.
By using closure properties.
Some intuitions:
If the number of states which will occur is finite, the language is probably regular.
Otherwise, it is non-regular.
How to prove that a given language is not regular ?
By using pumping theory for regular languages.
By using Myhill-Nerode theorem.
By using closure properties.