Hey Everyone, Post your solutions to the Apr 12 In-Class Exercise here. Best, Chris

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

-- Apr 12 In-Class Exercise

1. A DFA that accepts inputs of size @BT@n@BT@ has at most @BT@n@BT@ many states. We can keep track of which state a DFA is in with only @BT@log n@BT@ many bits. 2. We can recognize the language of correctly matched parentheses of size @BT@n@BT@ by tracking how many open parentheses we have found so far: incrementing when we encounter an open, and decrementing when we encounter a closed. In a string of size @BT@n@BT@ matching parentheses, there will only be up to @BT@n/2@BT@ open parentheses, and in the worst case we can track them with @BT@log(n/2)@BT@ bits. 3. Create a configuration graph for a PDA accepting some language. If this configuration graph can find a path between a start and accept state (using our NL algorithm PATH), the language is in NL.

-- Apr 12 In-Class Exercise

1. A DFA has finite number of states, we can design the automata so that on successfully accepting the string it writes 0 to the output tape else it writes 1. This uses constant space so we can say that languages decided by DFA are in logspace 2. we count the number of parenthesis. incrementing when we see a opening parenthesis and decrement it when we encounter a closing parenthesis 3. Languages recognised by a PDA grow in linear way as they use a stack, if a CFL would be similar to the PATH problem which we defined in class then we could say that it is in NL.

-- Apr 12 In-Class Exercise

1. In DFA we are storing information of only current state. If DFA has n input states then each state can be represented by at most log(n) bits. Hence DFA is in logspace L. 2. In the language of correctly matched parenthesis, maintains a count of unmatched pairs. If opening parenthesis is encountered then increament counter. If closing parenthesis is encountered then decreament the counter. For n parentheses, we need atmost log(n) bits to maintain the count. Hence It is in L. 3. Since for languages recognized by PDA stacks are updated in linear was. We need to check complete stack to verify whether the language is in NL. Hence it is harder do determine that the language is in NL.

-- Apr 12 In-Class Exercise

• DFA has K states where K is a constant: this requires a fixed amount of memory, which is in O(log(n)) • Parenthesis Language is in LOGSPACE, because all one needs to do is count parenthesis (adding or subtracting one at each symbol), and counting takes O(log(n)) • A stack is required to keep track of arbitrary symbols, and a stack can grow linearly, which is larger than LOGSPACE

-- Apr 12 In-Class Exercise

#Since we have finitely many states, we will simulate the input on a TM with the same amount of states, and would only require an additional write space for the output. This can be done in constant space. #First we need to count the number of parenthesis which can be done in n/2 time, and keeping track of left vs right parenthesis which can be done in log space. #Since we have to keep track of the stack, there could be n many symbols to write on the work tape, which would be greater than logspace. Suppose we had a stack with log many symbols, this can be done in NL-space.

-- Apr 12 In-Class Exercise

1. Since a DFA has finite states, an automata which when successfu;;y accepts the string writes 0 else writes 1 cane be designed. SInce this uses constant space, languages decided by DFA are in logspace 2. Count number of open and close parenthesis and if there is a mismatch, reject it 3 .Since languages recognised by a PDA use stack, they grow in linear time. If a CFL is similar to PATH problem, we can say that it is in NL

-- Apr 12 In-Class Exercise

(i) We could encode all the states of DFA in the input tape of the turing machine. We can output 1 if accept state is reached else 0. So it would take 1 tape square 1 is less than log space. (ii) The parathesis matching can be done as given: for every open paranthesis we increment the count and for closed paranthesis we decrement the count and when we finish parsing the input the count should be 0 if the parathesis match. So it would take atmost log(n/2) space. (iii)To check if a language is recognized by PDA, we use PATH algorithm which uses stack. The inputs put into a stack, the stack would grow linearly which is in NL.