CSIS-351: Discrete IITest - Chapter 2 & 3Name: ______
1.[12] What classes of languages are described below, i.e.,Regularand/orContext-free. Circle all thecorrect class descriptions.
A = {anbncn | Ʃ = {a,b,c}, n >= 0 }RegularContext-free
B = { w | Ʃ = {0,1} and
w has twice as many 0’s as 1’s }RegularContext-free
C = {an | Ʃ = {a}, n = 2i andi 0}RegularContext-free
D ={ an | Ʃ = {a}, n = 2i and i >= 0}RegularContext-free
[10] Pick one of the languages above that is NOT context-free and prove itusing the pumping lemma. Be sure to state the three conditions of the pumping lemma. You can use a combination of words and drawings to make your proof.
By the pumping lemma, if A is context-free then si=uvixyiz Afor all value of isuch that
|vxy| <= p and |vy| > 0
Set s = uvxyz= apbpcp A and consider the example where p = 3 such that s = aaabbbccc
While it is possible for v to consist of a’s and b’s, there are p=3 b’s and |vxy | <= 3. Thus, it is impossible for y to consist of c’s. Hence we cannot equally pump up a’s, b’s, and c’s. Similarly, while it is possible for v to consist of a’s, y cannot consist of both b’s and c’s because this implies that vxy would have to consist of 5 or more characters, which is greater than p
Thus only five possible configurations arise:
- vxy is entirely composed of a’s. Thus, we can pump up a’s without pumping up b’s or c’s
- vxy is entirely composed of b’s. More b’s than a’s or c’s,
- vxy is entirely composed of c’s. More c’s than a’s or b’s
- v consists of a’s and y consists of b’s, i.e., number of a’s and b’s will be greater than c’s
- v consists of b’s and y consists of c’s, i.e, number of b’s and c’s will be greater than a’s
In all 5 cases, the number of a’s, b’s, and c’s will not match since you can pump up the v and y components, i.e., si=uvixyiz A
By the pumping lemma, if C is context-free then all si=uvixyiz C where |vxy| <= p and |vy| > 0
Set s = uvxyz= apCand for illustration consider p = 21 = 2, i.e., s = aa
First, in all configurations were vxy consists of a single a, one pump up, i.e., s2 =uv2xy2z = aaa, yields a string with three as which is clearly not a power of 2, i.e, is not in C.
Second, note that there are four possible ways for vxy to consist of all two a’s
- v = aa with u, x, y and z being empty
- v = a, y = a, with u, x and z being empty
- y = aa with u, x, v and z being empty
And, in all cases one pump up, i.e., s2 =uv2xy2z = aaaa, yields a string in A, i.e., s2C. However, a second pump up s3 =uv3xy3z = aaaaaa, yields a string with six a’s which is clearly not a power of 2, i.e., s3 C
Finally, since vy cannot be empy. We cannot consider configurations where vxy consists of zero a’s.
Thus, there exists no configurations such that all siC for all i’s.
2.Consider this language:
E = {0n1m | Ʃ = {0,1}, m = 2n and n 0 }
[4] List the first 4 strings in this language, i.e., n=1, 2, 3, and 4
011001111 000111111000011111111
[10] Show the PDA state diagram for accepting the language E.
3.Consider the following grammar
S F(P,P)
P P,P | v
F min | max | ave
whichcan generate strings such as max(v,v) or min(v,v,v).
[4] First, extend the grammar so that it can also generate nested function calls such as max(max(v,v), min(v,v,v)). Show only the additional production rule(s) needed to create nested function calls.
PS
[8] Second, extend the grammar so that is can also generate strings of the form:
max(v,v,v)+ave(v,v) and max(v,v)-min(v,v), where the valid operators are +, -, * and /. Show only the additional production rule(s) needed to create these additional types of expressions.
SSOS
O+ | - | * | /
4. Consider this language
A = {axbycz | Ʃ = {a,b,c}, x = y or y = z, x > 0, y > 0, z > 0 }
[8] Can this language be accepted by a deterministic PDA? Yes or no.
Justify your answer with a proof, explanation or machine description?
When you encounter the first a, you cannot decide deterministically whether to push it (which is necessary to match the a’s and b’s, i.e., x = y) or ignore it (which is necessary in order to match the b’s and c’s, i.e., y = z). If you decide not to push the a’s, then you’ll have no way to determine if they match the b’s. However, if you do decide to push and pop a’s to verify that they match the b’s, then there is no way to push and pop (i.e., remember) the b’stoverify that they match the c’s. Thus, the only way to accept strings in this language is to explore both options, which requires a non-deterministic transition.
[8] Can this language be generated by a Context-free Grammar? Yes or no.
Justify your answer with proof, explanation, or an actual grammar.
S = XC | AY// Choose to match a’s and b’s (XC) or b’s and c’s (AY)
A = aA | a// Generate one or more a’s
C = cC | c// Generate one or more c’s
X = aXb | ab// Generate an equal number of a’s and b’s
Y = bYc | bc// Generate an equal number of b’s and c’s
[4] What do these answers tell you about the power Context-free Grammars vs. deterministicPDAs?
Context-free Grammars are more powerful than deterministic PDAs because some context-free languages (like the one above) require making a non-deterministic decision. In a Context-free Grammar, non-determinism is implemented in production rules (i.e., S = XC | AY) that allow for two entirely different string derivations. The transitions of a deterministic PDA cannot account for such string derivations.
5.[10] Consider this grammar
S A | B | C | AB | BC | AC | ABC | ɛ
A aA | a
B bB | b
C cC | c
What kind of language is it (Regular, Context-free, Turing Decidable or Turing Recognizable)? Explain your answer with the most appropriate proof (pumping lemma) or evidence (construct a machine).
This language is Regular, which also means that it is Context-Free, Turing Decidable and Turing Recognizable.
a*b*c*
6. [20] Write a Turing Machine implementation, i.e, state diagram, that counts the number of a’s in a string and writes the answer in binary immediately to the left of the string. Assumptions: Ʃ = {a}, Γ = {a, 0, 1, _}, infinite tape to the right and left where the read/write head points to the left-mosta.
Input: … _ _ _ _ a _ _ …Output: … _ _ _ 1 a _ _ …
Input: … _ _ _ _ a aaa _ _ …Output: … _ 1 0 0 a aaa _ _ _ …
Input: … _ _ _ _ a aaaa _ _ …Output: … _ 1 0 1 a aaaa _ _ …
Use the following informal description to maximize partial credit.
- [2] Move to the right-most a
- [4] Moving right to left, replace every othera with an x starting with the right-most a.Be sure to move right to left over previously written x’s
- [8] Replace the blank _ closest to the left-mosta with either 1 or 0. Be sure to skip over any previously written 1’s and 0’s. Figuring out whether or not to write a 1 or 0 depends on whether the a’s were even or odd, which you can determine based on which state you were in when you finished step 2 above.
- [6] Repeat steps 1-3 until there are no more a’s and move to an accept state. There is no rejection. Acceptance mean the output is available.
7. Given the following Turing Machine
Assumptions:
Ʃ = {a,b} and Γ = {a,b, _}
The read/write head points to the left-most input symbol. The tape is infinite to the right and left and padded with blanks _. If no transition can be taken, automatically reject, i.e., every missing transition goes to the reject state.
- [5] Show the sequence of configurations for input string: bbaa
_bbaa_ _ _baa_ move right over baa _ _ ba _ _ _ _ b _ _ _
move left over b ______ reject, we are in the 3rd state from the top and the only valid transition is on an ‘a’ and the read head points to a ‘_’
- [1]Is this string accepted or rejected? Circle one:AcceptedRejected
- [2] Given one example of an accepted string baa
- [4] Give two examples of rejected stringsab baaa
- [6] Describe the language accepted by this Turing Machine using the most appropriate and minimal description.
A = {bnam | m = 2n and n>=0 }
8. [20] Describe informally, i.e, no state diagram, a Turing Machine that can compare two binary numbers that are separated by a #. After comparing, the # is replaced with an appropriate operator , , or = indicating the result of the comparison.
Input: … _ 0 1 0 # 0 1 1 _ _ …Output: … _ 010011 _ _ …
Input: … _ 0 1 0 # 0 0 1 _ _ …Output: … _ 010001 _ _ …
Input: … _ 11 0 # 1 1 0 _ _ …Output: … _ 110 = 110 _ _ …
Assumptions:
Ʃ = {0,1,#} and Γ = {0,0, 1, 1, #,,,=}
The read/write head points to the left-most input symbol. The tape is infinite to the right and left and padded with blanks _.
To maximize your score, provide a general explanation first. Then, describe the details. More details means more points.
[See working simulation]