tag:blogger.com,1999:blog-8496373585700416995.post7280370525269308061..comments2023-06-18T20:13:49.867+08:00Comments on Dream & Passion: QE notesAnonymoushttp://www.blogger.com/profile/09375125981129389911noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-8496373585700416995.post-84072509307522105352009-04-05T14:11:00.000+08:002009-04-05T14:11:00.000+08:00How to prove a language is regular ? Design FA f...How to prove a language is regular ?<BR/> Design FA for the language.<BR/> Design regular expressions for the language.<BR/> By using closure properties.<BR/>Some intuitions:<BR/>If the number of states which will occur is finite, the language is probably regular.<BR/>Otherwise, it is non-regular.<BR/><BR/>How to prove that a given language is not regular ?<BR/>By using pumping theory for regular languages.<BR/>By using Myhill-Nerode theorem.<BR/>By using closure properties.Anonymoushttps://www.blogger.com/profile/09375125981129389911noreply@blogger.comtag:blogger.com,1999:blog-8496373585700416995.post-8062893725925316472009-04-05T12:12:00.000+08:002009-04-05T12:12:00.000+08:00FOL: Conversion to CNF1.Eliminate biconditionals a...<B>FOL: Conversion to CNF</B><BR/><BR/>1.Eliminate biconditionals and implications;<BR/>2.Move negation inward;<BR/>3.Standardize variables: each quantifier should use a different one;<BR/>4.Skolemize: a more general form of existential instantiation: <B><I>Each existential variable is replaced by a Skolem function of the enclosing universally quantified variables</I></B>;<BR/>5.Drop universal quantifier;<BR/>6.Distribute and over or.Anonymoushttps://www.blogger.com/profile/09375125981129389911noreply@blogger.comtag:blogger.com,1999:blog-8496373585700416995.post-69539025352946616342009-04-05T11:53:00.000+08:002009-04-05T11:53:00.000+08:00Universal Instantiation UI can be applied many tim...<B> Universal Instantiation </B><BR/>UI can be applied <I><B>many times</B></I> to add new sentences. The new KB is equivalent to the old one.<BR/><BR/><B> Existential Instantiation </B><BR/>EI can be applied <I><B>only once</B></I>. The new KB is not equivalent to the old one. But they are equivalent in the degree of satisfiable.Anonymoushttps://www.blogger.com/profile/09375125981129389911noreply@blogger.comtag:blogger.com,1999:blog-8496373585700416995.post-35209534979394264212009-04-03T17:15:00.000+08:002009-04-03T17:15:00.000+08:00Equivalence RelationLet A be a set and ~ be a bina...<B>Equivalence Relation</B><BR/><BR/>Let 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:<BR/>Reflexivity: a ~ a<BR/>Symmetry: if a ~ b then b ~ a<BR/>Transitivity: if a ~ b and b ~ c then a ~ c.<BR/>The equivalence class of a under ~, denoted [a], is defined as . A together with ~ is called a setoid.<BR/><BR/>http://en.wikipedia.org/wiki/Equivalence_relationAnonymoushttps://www.blogger.com/profile/09375125981129389911noreply@blogger.com