Theory of Computation HW5 Solutions (57 points total)
Questions related to Ch 2.2: 2.5 (22), 2.10 (10), 2.16 (15), 2.22 (0), 2.26 (10)
2.5 (22 points total; 4 points each part except 2 points for part f). Give informal descriptions of pushdown automata for the languages in Exercise 2.4 You need not provide the state transitions.
a) {w| w contains at least 3 1’s} This language is regular, so the PDA doesn’t need to use its stack. The PDA reads the input and uses its finite control to maintain a counter which counts up to 3. It keeps track of the number of 1s it has seen using this counter. The PDA enters an accept state and scans to the end of the input if it has read 3 1’s.
Copyright By PowCoder代写 加微信 powcoder
b) {w| w starts and ends with the same symbol} The language is regular. The PDA reads the input and keeps track of the first and last symbol in its finite control. If they are the same, it accepts, otherwise it rejects.
c) {w| the length of w is odd} This language is regular. The PDA reads the input and keeps track of the length (modulo 2) using its finite control. If the length is 1 (modulo 2) it accepts, otherwise it rejects.
d) {w| the length of w is odd and the middle symbol is a 0} The PDA reads the input and pushes the symbols onto the stack. At some point it nondeterministically guesses where the middle is. It looks at the middle symbol. If that symbol is a 1, it rejects. If it is a 0 then PDA reads the rest of the string, and for each character read, it pops one element off of its stack. If the stack is empty when it finishes reading the input, it accepts. If the stack is empty before it reaches the end of the input, or nonempty when the input is finished, it rejects.
e) {w | w is a palindrome} The PDA reads the input and pushes each symbol onto the stack. At some point it nondeterministically guesses when it has reached the middle. It also nondeterministically guesses whether the string has odd length or even length. If it guesses even, it pushes the current symbol it’s reading onto the stack. If it guesses the string has odd length, it goes to the next input symbol without changing the stack. Then it reads the rest of the input, and it compares each symbol it reads to the symbol on the top of the stack. If they are the same, it pops the stack, and continues reading. If they are different, it rejects. If the stack is empty when it finishes reading the input, it accepts. If the stack is empty before it reaches the end of the input, or nonempty when the input is finished, it rejects. (Do not take off points if the student does not handle the even and odd cases and treats things like they are all even or odd)
f) The empty set. The PDA never enters any accept state.
2.10 (10 points) Given an informal description of a PDA that recognizes the language A = {aibjck| i=j
or j=k, where i, j, k ≥ 0}
Here is the description in steps:
1. Nondeterministically branch to either step 2 or step 5
2. Read and push a’s
3. As long as input is “b” read b’s while popping a’s. If no a to pop then reject.
4. If b’s finish when stack is empty, skip c’s on input and accept. If see “a” or “b” when skipping c’s, enter reject state and skip rest of input.
5. Skip a’s on input
6. Read and push b’s
7. Read c’s, while popping b’s (if no b to pop then reject). If see an “a” or “b” enter reject
state and skip rest of input.
8. If c’s finish when stack is empty, accept.
2.16 (15 points) Show that the class of context-free languages is closed under the regular operations of union, concatenation, and star.
Let G1 = (V1, , R1, S1) and G2 = (V2, , R2, S2) be CFLs.
Construct a new CFG Gu where L(Gu) = L(G1) L(G2). Let S be a new variable that is neither in V1 nor V2 and assume these sets are disjoint.
Let Gu =(V1V2{S},,R1R2{r0},S},wherer0 isS→S1|S2.
Concatenation
We construct CFG Gc that generate L(G1) L(G2). Let S be a new variable that is neither in V1 nor V2 and assume these sets are disjoint.
LetGc =(V1V2{S},,R1R2{r0},S},wherer0 isS→S1S2.
Construct a new CFG G* that generates the language L(G1)*. Let S be a new variable not in V1 andmakeitthestartingvariable.Letr0 beS→SS1|εbeanewruleinG* (S1istheoriginal start variable)
2.22 (not graded) Let C = {x#y| x, y {0,1}* and x ≠ y}. Show that C is a context-free language.
We construct a PDA P that recognizes C. It operates by guessing corresponding positions on which the strings x and y differ. Note that this is much harder than palindromes, because we need to check if x = y and if we just push the symbols of x onto the stack, they are in the wrong order for just checking if those symbols equal those in y. So, we need to record the position that we are guessing has a difference, so we know how far to go after the # to check. We do this by pushing a 1 (or in fact any symbol) prior to the symbol we guess differs in x. Then, after scanning to #, we pop those 1’s and when we run out were are at the corresponding position in y. We then check to see if they are equal. If not, we know x ≠ y and accept. If they are equal, then we reject on this branch. As long as one branch finds a difference, the string will be accepted.
Here again is the procedure:
It reads the input at the same time that it pushes a 1 onto the stack. At some point it nondeterministically guesses a position in x and it records the symbol it is currently reading there in its finite memory and then skips to the # (at this point the number of symbols on the stack will tell the PDA how far to go after the # before checking for a matching symbol). Then it pops the stack while reading symbols from the input until the stack is empty and checks that the symbol it is not currently reading is different from the symbol it has recorded. If so, it accepts.
Here is a more detailed description of P’s algorithm. If something goes wrong, for example, popping when the stack is empty, or getting to the end of the input prematurely, P rejects on that
branch of the computation.
1. Read next input symbol and push 1 onto the stack
2. Nondeterministically jump to either 1 or 3
3. Record the current input symbol a in the finite control
4. Read input symbols until # is read
5. Read the next symbol and pop the stack
6. If the stack is empty, go to step 7, otherwise go to step 5
7. Accept if the current input symbol isn’t a, otherwise reject.
2.26 (10 points) Show that if G is a CFG in Chomsky normal form, then for any string w L(G) of length n ≥ 1, exactly 2n -1 steps are required for any derivation of w.
First, Chomsky normal form means that every rule is of the form: A → BC
Now, we always start with the start symbol, a variable (not a terminal symbol). A derivation should yield only terminal symbols. So, first we need to increase the number of variables to match the length of w, which is n, and then we need to replace each variable with a symbol. We start with a single variable. To increase the length we therefore need n – 1 applications of rules of the form A → BC. Then we need to apply n applications of rules of the form A → a. Thus we need n-1 + n = 2n-1 steps.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com