Theory of Computation ppt.
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
seminar surveyer
Active In SP
**

Posts: 3,541
Joined: Sep 2010
#1
07-01-2011, 12:22 PM





.ppt   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



Reply
seminar ideas
Super Moderator
******

Posts: 10,003
Joined: Apr 2012
#2
05-05-2012, 04:39 PM

Theory of Computation



.pdf   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
Reply
seminar flower
Super Moderator
******

Posts: 10,120
Joined: Apr 2012
#3
03-08-2012, 04:29 PM

Theory of Computation


.ppt   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.


Reply

Important Note..!

If you are not satisfied with above reply ,..Please

ASK HERE

So that we will collect data for you and will made reply to the request....OR try below "QUICK REPLY" box to add a reply to this page

Quick Reply
Message
Type your reply to this message here.


Image Verification
Please enter the text contained within the image into the text box below it. This process is used to prevent automated spam bots.
Image Verification
(case insensitive)

Possibly Related Threads...
Thread Author Replies Views Last Post
  Computational Methods for a Mathematical Theory of Evidence seminar projects maker 0 275 30-09-2013, 04:24 PM
Last Post: seminar projects maker
  Programming Language Theory ICS313 seminar projects maker 0 321 24-09-2013, 02:03 PM
Last Post: seminar projects maker
  Game Theory in Wireless and Communication Networks: Theory, Models, and Applications study tips 0 391 22-08-2013, 03:29 PM
Last Post: study tips
  DATABASE THEORY PPT study tips 0 323 03-06-2013, 04:25 PM
Last Post: study tips
  Fast Fourier Transform (FFT) (Theory and Implementation) study tips 0 423 22-05-2013, 04:49 PM
Last Post: study tips
  Number Theory Algorithms and Cryptography Algorithms PPT study tips 0 389 20-05-2013, 04:25 PM
Last Post: study tips
  Rethinking of computation for future-generation, knowledge-rich speech recognition study tips 0 302 02-03-2013, 12:03 PM
Last Post: study tips
  Distributed computation, analysis, and presentation between PCs ppt study tips 0 294 26-02-2013, 04:41 PM
Last Post: study tips
  Queueing Theory pdf study tips 0 303 14-02-2013, 03:58 PM
Last Post: study tips
  SecuredTrust: A Dynamic Trust Computation Model for Secured Communication Report study tips 0 347 11-02-2013, 09:38 AM
Last Post: study tips