Theory of Computation ppt.
• 0 Vote(s) - 0 Average
• 1
• 2
• 3
• 4
• 5
 seminar surveyer Active In SP Posts: 3,541 Joined: Sep 2010 07-01-2011, 12:22 PM   Introduction to TOC.ppt (Size: 41.5 KB / Downloads: 104) What is ToC? What can or cannot be computed efficiently with given resources Can it be computed?- Computability Theory Can it be computed quickly? – Complexity Theory Computability Theory Problems Solvable Not solvable Complexity Theory Computationally Hard Problems Computationally Easy Problems Defining ToC Fundamental ideas & Models on Computing The branch of computer science and mathematics that deals with how efficiently problems can be solved on a model of computation, using an algorithm. Computational Model Automata Alphabets Strings Empty string Length of a string Powers of an alphabet Concatenation of strings Languages
 seminar ideas Super Moderator Posts: 10,003 Joined: Apr 2012 05-05-2012, 04:39 PM Theory of Computation   toc-2.pdf (Size: 475.44 KB / Downloads: 87) Examples of Regular Expressions Given  = {a, b}. The following are regular expressions specifying languages over . ab + ba specifies a language that only contains ab and ba. a*b* specifies a language that contains only strings of any number of (or 0) a’s followed by any number of (or 0) b’s. (ba)* specifies a language that contains only strings containing a number of (or 0) repetitions of ba. (ba)* + a*b* specifies a language that contains a string iff the string is contained by either of the two previous languages. (ba)*(ab + bba + L) specifies a language that contains strings starting with a number of (or 0) repetitions of ba followed by ab, bba or nothing. Construct DFAs from the following expressions Given  = {a, b}. The following are regular expressions specifying languages over . ab + ba specifies a language that only contains ab and ba. a*b* specifies a language that contains only strings of any number of (or 0) a’s followed by any number of (or 0) b’s. (ba)* specifies a language that contains only strings containing a number of (or 0) repetitions of ba. (ba)* + a*b* specifies a language that contains a string iff the string is contained by either of the two previous languages. (ba)*(ab + bba + L) specifies a language that contains strings starting with a number of (or 0) repetitions of ba followed by ab, bba or nothing. Negation of a Language, L1 For DFA1, construct DFA2 which includes explicitly mentions all the missing transitions leading to a failure state f. Construct DFA3, which is copy of DFA2 with all the accepting states in DFA2 as nonaccepting states in DFA3 and all the other states in DFA2 as accepting states in DFA3. Make sure that f is an acceptance state. DFA3 now accepts the complement of L1
 seminar flower Super Moderator Posts: 10,120 Joined: Apr 2012 03-08-2012, 04:29 PM Theory of Computation   1Theory of Computation.ppt (Size: 259 KB / Downloads: 37) IMPORTANT NOTES Students… This presentation is designed to be used in class as part of a guided discovery sequence. It is not self-explanatory! Please use it only for revision purposes after having taken the class. Simply going through the slides will teach you nothing. You must be actively thinking, doing and questioning to learn! Course Strategy Be Warned: This is not a course that spoon-feeds students. Students are expected to be investigative and resourceful. Reading books and other research of topics are expected. Regular Expression Definition A regular expression, or RE, describes strings of characters (words or phrases or any arbitrary text). It's a pattern that matches certain strings and doesn't match others. A regular expression is a set of characters that specify a pattern. OR Language defining symbols. Regular expressions are used to generate patterns of strings. A regular expression is an algebraic formula whose value is a pattern consisting of a set of strings, called the language of the expression. Operands in a regular expression Operands in a regular expression can be: characters from the alphabet over which the regular expression is defined. variables whose values are any pattern defined by a regular expression. epsilon which denotes the empty string containing no characters. null which denotes the empty set of strings.