All Questions
Tagged with reference-question automata
4 questions
1
vote
1
answer
74
views
Does Sipser's _Introduction to the Theory of Computation_ cover the Chomsky hierarchy?
I saw the book suggested here.
Does Sipser's Introduction to the Theory of Computation cover the Chomsky hierarchy?
I ask since, looking through a pdf copy of the book, I found no matches with "...
- 207
15
votes
3
answers
1k
views
Why nondeterminism?
Theory of computation often involves nondeterministic models of computation. Some examples include nondeterministic finite automata (NFAs), nondeterministic pushdown automata (PDAs), and ...
- 280k
21
votes
1
answer
18k
views
How do I write a proof using induction on the length of the input string?
In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
- 313
55
votes
9
answers
133k
views
How to prove a language is regular?
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?
For instance, if I am given that $L$ is regular,
how can I prove that ...
- 899