Q6: 1.55cegh
(c) L = 001 U 0*1*
The minimum pumping length is one.
Consider a FSA that accepts L.
The minimum pumping length cannot be zero because the empty string is in the language L and the empty string could be accepted by the FSA without visiting any states that might trigger a loop.
It sufficient to provide the smallest possible string in the language such we visit a state that participates in a loop. If we visit such a state, we can exploit the loop and pump up the string.
The * operator is implemented as a FSA loop.
A pumping length of one implies a string that is long enough such that either the 0* or 1* loops are visited.
In fact,
0 must exploit the 0* loop
1 must exploit the 1* loop
(e) L = (01)*
The minimum pumping length is one.
Similar to the example above, a minimum pumping length of zero allows us to use the empty string as an example, which doesn’t guarantee that we will visit states that participate in a loop.
Why isn’t the pumping length two?
The string must be in the language and must be longer than the pumping length. The language above cannot have a string of length one, so even with a pumping length of one, we have to select the next biggest string, i.e, length two. We are forced to pick the second shortest string in L, i.e., 01, which forces us to visit the states which implement the (01)*.
(g) L = 1*01*01*
The minimum pumping length is 3.
First, a minimum pumping length of one or two allows us to select s = 00 as a candidate string. The FSA could be implemented such that no loop is exploited for the string 00.
However, a minimum pumping length of three forces the string to have at least one 1. The string could be 100, 010, or 001.
In all three cases, this input must allow us to visit one of the states that implements one of the 1* loops.
(h) L = 10(11*0)*0
The minimum pumping length is 4.
Similar to question (e), we must select a string in the language that is greater than the minimum pumping length. This forces us to select the string 10100, which allows us to reach a state that is part of the (11*0)* loop. A pumping length of one, two, or three are too small because that would allow us to pick string 100, which may not visit a state that participates in the (11*0)* loop.
Q7:
Given the alphabet {1} where e is the empty string and the following productions rules:
S --> 1S11 | 11S1 | e
a) Describe the language in English
The language includes the empty string and all string consisting of all 1’s where the number of 1’s is a multiple of three, i.e, {e, 111, 111111, 111111111, …}
b) Is the language Regular? If so, express it as a Regular Expression. If no, prove it using the pumping lemma
Yes, (111)*
c) Is the language Context Free? Explain.
Yes, all Regular languages are also context free by definition. If the language can be accepted without a stack, it can be accepted with a stack.
Q8:
Given the alphabet {0,#} and the following productions rules:
S --> TX
T --> 0T00 | #
X --> 00X0 | #
a) Describe the language in English
The language consists of strings of the following format:
0x#02x+2y#0y
The number of zeros between the two #’s is twice the sum of the zero before first # and after the second #.
b) Is the language Regular? If so, express it as a Regular Expression. If no, prove it using the pumping lemma
s = 0p#02p+2p#0p = 0p#04p#0p
s = xyz
|xy| <= p
|y| > 0
xy must contain all zero before the first #
y must contain at least one zero before the first #
By pumping up y i times we yield
Si = 0p+i#04p#0p
Si is not in the language because the number of zeros between the two #’s is NOT equal to twice the sum of the zero before first # and after the second #. We can add i zeros before the first # without increase the number of zeros between the #’s
c) Is the language Context Free? Explain
Yes, because a Context Free Grammar defines Context Free languages.
Q9: 2.6b
S XbXaX | T | U
T aTb | Tb | b
U aUb | aU | a
X aX | bX |
Q10: 2.7b
e is the empty string
First, push a “#” onto the stack (e, e #) and consume no input.
Second, if the input is “b” move to an accept state and consume all the remaining input.
Strings starting with “b” are in the complement of anbn so we can safely accept and terminate.
Otherwise, if the input is “a,” push an “a” and move to the “A-state,” which is an accept state
From the A-state, keep pushing a’s until you encounter a “b.”
If you never encounter a “b”, then you know you have at least one “a” and no b’s, so you can safely accept and consume all input.
As soon as you encounter a “b,” pop an “a” and move to the “B-state,” which is a reject state. There will be at least one “a” to pop because we came from the “A-state” which required encountering at least one “a.” We just encountered a “b,” so there is a chance we’ve consumed exactly one “a” and one “b,” so the string might have an equal number of a’s and b’s. This is why “B-state” must be a reject state.
In the B-state, we will pop an “a” only if we encounter a “b” (b,a e).
To get out of this reject state, three things have to happen.
First, we might encounter another “a,” which means we have an “a” following a “b,” which is certainly in the complement of anbn. Thus, we can move to an accept state and consume all the input.
Second, we might encounter a “b” with a “#” on the stack, which means we have more b’s than a’s. Thus we can accept and consume the remaining input.
Third, we may have consumed all the input and there are still a’s on the stack; Thus, we have more a’s than b’s and we can accept. But, we cannot foresee when the input will be consumed, so we have to non-deterministically move to an accept state, i.e, e,ae. But, we don’t pop an “a.” (e,a e). From this state, if we still have input to consume, we have to move back to the “B-state” but only if the input is a “b” and the stack is “a.” We also must pop the “a.” But, if the input is an “a,” we move to the “a follows b” accept state. If the input is a “b” and the stack is #, we move to the “more b’s” accept state.
We only remain in the “B-state” after full input consumption if there is a # on the stack, which means there must have been an equal number of b’s for every “a” and the b’s strictly followed the a, i.e. no “a” after a “b.”
Q11:
Design and implement a Turing Machine that will accept the following language.
The alphabet is {a,b,c}
A = {anbncn | n > 1}
Q1: If the string is empty (_) reject
Only move forward if it starts with one “a,”
Q2: then move the pointer back to the first “a”
Q3-Q6: moves left to right replacing one a, one b, and one c each with one x.
Q7: move back to the left-most position.
In Q3, we reject if we hit an un-matched a,b or c
In Q4, we reject if we hit an un-matched b or c
In Q5, we reject if we hit an un-matched c
In Q3, we only accept if we’ve replaced all the a’s, b’s, and c’s with x’s.
We never reach Q3 unless we are sure we have one “a.” We only loop back to Q3 if we have done a complete replacement iteration Q3 to Q7. We can only hit _ in Q3 if the tape is all x’s