-- Apr 12 In-Class Exercise
1. We could encode all states of a DFA into a turing machine and move from current state to the other based on the input.
At the end of the input, if the current state we are in is the special final state, then we write 1 to the output tape.
This takes 1 tape square which is within log space, L.
2. For correctly matched parenthesis, to recognise correctly matched pairs of parenthesis, we could count up when we see an opening parenthesis, and count down when we see a closing parenthesis.
This will take at most log space to store the count of half the length of a correctly matched pairs.
3. Languages recognised by a PDA use a stack which could grow at a rate linear to the input which is not contained in NL. For a language recognised by PDA to be in NL, it would have to be similar to the PATH problem where we were checking for paths of at most 2^i in length.
(
Edited: 2017-04-12)
1. We could encode all states of a DFA into a turing machine and move from current state to the other based on the input.
At the end of the input, if the current state we are in is the special final state, then we write 1 to the output tape.
This takes 1 tape square which is within log space, L.
2. For correctly matched parenthesis, to recognise correctly matched pairs of parenthesis, we could count up when we see an opening parenthesis, and count down when we see a closing parenthesis.
This will take at most log space to store the count of half the length of a correctly matched pairs.
3. Languages recognised by a PDA use a stack which could grow at a rate linear to the input which is not contained in NL. For a language recognised by PDA to be in NL, it would have to be similar to the PATH problem where we were checking for paths of at most 2^i in length.