Where can I find good explanations of Computability and Complexity?

159 Views Asked by At

I have a repeat coming up in Computability and Complexity and I was wondering if anybody has good resources for this sort of study. Things like regular languages, context free and context sensitive languages and all that sort of stuff.

For example:

enter image description here

As you can see, it is a horribly phrased question. The notes our lecturer gave us are equally as bad. I really need to pass this module so if anybody has a good resource for studying these topics it would be much appreciated.

2

There are 2 best solutions below

0
On

You may want to look at the class notes made available by Avi Kak at https://engineering.purdue.edu/kak/courses-i-teach/ECE664/Index.html
See the handwritten notes on Lecture 17 that explain the notation in your question.

1
On

I think the problem you're having is not the fault of the phrasing, but the fact that you're not yet comfortable dealing with the mathematical notation involved.

Wikipedia has a lot of articles on automata and other computer science theory topics. Also, a google search on 'NFA to DFA' turns up many helpful results. Automata are used heavily in compilers, so you might find a more "practical" explanation of things in material from a compilers course.

Your class is going to be heavily mathematical, though, so you would do best for yourself by putting aside the attitude that the material you've been given is poor and spend the time learning to understand it. Mathematical formulations give you precise and concise descriptions without as much room for misinterpretation as informal language has.