Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSE 103 Computational Models
(Note: This answer key uses the question variants from Version A of the midterm.)
1. (80 pts.) True or false?
State whether each of the following statements is true or false (without giving a justification). Make sure to
read each statement carefully.
(a) An NFA N = (Q,Σ,δ ,q0,F) accepts w ∈ Σ∗ if and only if every state in δˆ (q0,w) is an element of F .
Solution: False: only a single state in δˆ (q0,w) needs to be an accepting state, not all of them (since
an NFA accepts an input if any of the possible paths end in an accepting state). Formally, acceptance
requires only that δˆ (q0,w)∩F 6= /0, as we stated in class.
(b) If an NFA N has no ε-transitions, then every word in its language has exactly one accepting path.
Solution: False: a state in an NFA can also have multiple transitions for a single input symbol, so that
multiple accepting paths might be labeled with the same word.
(c) You can test whether a word w ∈ Σn is in the language of an NFA in time linear in n (treating the size
of the NFA as a constant).
Solution: True: the simulation algorithm we described in class runs in time O(ns2) where s is the
number of states of the NFA.
(d) If we allowed transitions of an NFA to be labeled with regular expressions instead of individual sym-
bols, it would not expand the class of languages that NFAs can recognize.
Solution: True: recall that our procedure for converting a DFA to a regular expression began by
turning the DFA into a GNFA (generalized NFA), which is precisely an NFA whose transitions can
be labeled with regular expressions. The procedure would work equally well if we started with an
arbitrary GNFA, yielding a regular expression whose language was equal to that of the original GNFA.
Therefore the languages of GNFAs are regular, just as for ordinary NFAs.
(e) There exist languages which are regular but not context-free.
Solution: False: we proved that all regular languages are context-free (since if they can be recognized
by a DFA, they can be recognized by a PDA).
(f) For any alphabet Σ, we have {xy | x,y ∈ Σ∗}= Σ∗.
Solution: True: since ε ∈ Σ∗, for any x ∈ Σ∗ we can set y = ε and get xy = x. Conversely, any string
of the form xy with x,y ∈ Σ∗ is a string over Σ and so in Σ∗.
(g) If A and B are variables of a context-free grammar with terminal symbols Σ, and w ∈ Σ∗, then AB ∗=⇒ w
if and only if there exists some decomposition w= xy such that A ∗=⇒ x and B ∗=⇒ y.
CSE 103, Fall 2023, Midterm 1
Solution: True: since context doesn’t matter in a context-free grammar, a string is derivable from AB
if and only if A can derive some prefix of the string and B can independently derive the rest. We can
argue this more formally as follows. If A ∗=⇒ x and B ∗=⇒ y, then AB ∗=⇒ xy = w. Conversely, suppose
AB ∗=⇒ w: then w would be in the language of the grammar if we add the rule S→ AB. Taking a parse
tree for w under this expanded grammar, if we let x and y be the terminal symbols beneath A and B
respectively in the tree (in order from left to right), then we have A ∗=⇒ x and B ∗=⇒ y and also xy= w.
(h) For any language L recognized by a PDA P, there is a finite bound n (depending on L) such that P
never has more than n symbols on the stack when run on any w ∈ L.
Solution: False: the amount of stack space used when a PDA runs on an input word w can grow
arbitrarily large as the length of w increases. For example, if we run the PDA we saw in class for the
language L= {0n1n | n≥ 0} on the string 0m1m, it pushes m symbols on the stack. So there is no finite
upper bound on the size of the stack for all words in L.
(Note: In fact, if there is such a finite bound n then L must be regular, since there would be only
finitely-many possible contents of the stack (it being an element of Γ≤n, if Γ is the stack alphabet)
and so we could build an NFA which simulated P. So if L is not regular, any PDA for L must use an
unbounded amount of stack space.)
CSE 103, Fall 2023, Midterm 2
2. (80 pts.) Designing a DFA
Draw a DFA for the language L of strings over Σ= {x,y,z}where every substring xy is immediately followed
by a z (so zxxyz and yx are in L but xxy and xyxyz are not).
Solution: We need to keep track of whether we’ve just seen xy, rejecting if the string then ends or if we see
any symbol other than a z; otherwise we continue to monitor for xy (accepting if the string ends).
y,z
x
y
x
z
z
x,y
Σ
(Note the self-loop on symbol x in the second state: if we went back to the first state instead, we would
wrongly accept xxy since we would not detect the second x as the possible start of an xy substring. Also
notice that the third state is not an accepting state: otherwise we would allow an xy substring at the very end
of the string.)
CSE 103, Fall 2023, Midterm 3
3. (80 pts.) Interpreting an NFA
Consider the following NFA N with alphabet Σ= {x,y}:
1
2
3
4
y
ε
y
x
x,ε x
(a) For each of the following strings, state whether N accepts it, giving an accepting path if so:
• ε
Solution: Accepted along the (unique) path (2,3).
• yy
Solution: Accepted along the paths (2,3,3,3), (2,3,3,1), (2,3,3,1,2,3), etc.
• yx
Solution: Accepted along the (unique) path (2,3,1,2,3).
• xxxy
Solution: Rejected: notice that we cannot read more than 2 xs without passing through state 3,
but we cannot leave state 3 without reading a y.
(b) What is the language of N? (You may describe it in words; you do not need to give a justification.)
Solution: The language of N is all words over Σ which do not contain the substring xxx, i.e., the
words without three xs in a row. The observations in part (a) above show that any word containing xxx
can’t be accepted, since we can’t have more than 2 xs without a y in between. Any other word can
be accepted, however: we can reach state 3 without reading any symbols in, and can then accept any
number of ys before going back to state 2 in order to read one or two xs in and then repeat.
CSE 103, Fall 2023, Midterm 4
4. (80 pts.) Short answer
Give short (2-3 sentence) explanations of why the following statements are true. You may use any results
from class or the homework without further comment.
(a) If L is a regular language over Σ and w ∈ L, then the language L−{w} is also regular.
Solution: First observe that L−{w} = L∩{w}. The language {w} is regular because it is finite (as
we proved on HW 4), and since regular languages are closed under complement and intersection, so is
L−{w}.
(Note: It is not the case that a subset of a regular language is necessarily regular (consider the 0n1n
language, which is a subset of the regular language 0∗1∗); so the fact that L−{w} ⊂ L is not enough
to show that L−{w} is regular.)
(b) Given a language L over Σ, let L′ be the language of words which can be obtained by concatenating
between 1 and 3 words from L together. If L is regular, then so is L′.
Solution: If L is regular, there is a regular expression R such that L(R) = L. Then the regular expres-
sion R|RR|RRR matches words consisting of 1-3 words matching R (and therefore in L) concatenated
together: i.e., words in L′. Since regular expressions have regular languages, this shows that L′ is
regular.
Alternate Solution: If L is regular, the language LL consisting of two words from L concatenated
together is also regular, since the regular languages are closed under concatenation. By the same
argument, since LL is regular, so is LLL. Finally, regular languages are closed under union, so L∪LL∪
LLL= L′ is regular.
CSE 103, Fall 2023, Midterm 5
5. (40 pts.) Reading regular expressions
For each of the following pairs of regular expressions over Σ = {a,b,c}, state whether their languages are
equal (=), one is a proper subset of the other (⊂), or they are incomparable. If they are not equal, give an
example of a string that is in one language but not the other.
(a) R1 = ( /0 | ε)bc
R2 = ε | bc
Solution: We have R1 = ( /0 | ε)bc = /0bc | εbc = bc, since /0 matches no strings and so neither does
/0bc. Therefore R1 ⊂ R2, with the only string matching R2 that does not match R1 being ε .
(b) R1 = (a∗b∗c∗)∗
R2 = (b∗c∗a∗)∗
Solution: These expressions are equivalent: because all the subexpressions inside the parentheses are
starred, they can match the empty string and so be skipped; the outermost star then allows us to repeat
them any number of times. So changing the order of the subexpressions doesn’t change the language
(for example, to match abc with R1 we can use one copy of a∗b∗c∗, but we can also match it against
R2 by using two copies of b∗c∗a∗ where the b∗ and c∗ in the first copy and the a∗ in the second copy
match ε).
CSE 103, Fall 2023, Midterm 6
6. (100 pts.) The pumping lemma
With Σ= {a,b,c}, let L be the language {abic j | i> j ≥ 0} (so for example abbc and abbbbcc are in L, but
bbc and abc are not). Let’s use the pumping lemma to prove that L is not regular.
(a) Given n≥ 1, pick a word w ∈ Σ∗ for use in the pumping lemma.
Solution: We must pick a word which has length at least n and which is a member of L. One possibility
is w= abn+1cn: this is of the form abic j with strictly more bs than cs, as required.
(Note: Any fixed word not depending on n, like abbc, cannot work here, because we do not get to pick
the value of n: in order to invoke the contrapositive of the pumping lemma, the choice of w must work
for arbitrary n≥ 1 and so must depend on n.)
(b) Given a decomposition w= xyz with |xy| ≤ n and y 6= ε , choose a k ≥ 0 and argue that xykz 6∈ L.
Solution: Because |xy| ≤ n, both x and y can contain only as and bs. If y contains an a, then x must be
empty (since the only a is the first symbol of w), so if we pick k= 0, then xykz= xz= z will not contain
any as at all and so xykz 6∈ L as desired. If instead y does not contain an a, then since it is nonempty, it
must contain at least one b. In this case, again picking k = 0, the string xykz= xz will contain strictly
fewer bs than w but the same number of cs; so it will have < n+1 bs and n cs, and therefore will not
be in L. So no matter what decomposition the adversary picks, xy0z 6∈ L.
(Therefore, by the contrapositive of the pumping lemma, L is not regular.)
CSE 103, Fall 2023, Midterm 7
7. (80 pts.) Interpreting a CFG
Consider the following CFG G with terminal symbols T = {x,y,z}, variablesV = {A,B,C}, and start symbol
A:
A→ BAB | x
B→ y | z
(a) For each of the following words, state whether it is in L(G), giving a leftmost derivation if so:
• ε
Solution: This is not in L(G): there is no rule allowing a variable to expand into the empty string.
• yxy
Solution: This is in L(G): the unique leftmost derivation is A⇒ BAB⇒ yAB⇒ yxB⇒ yxy.
• yxxy
Solution: This is not in L(G): notice that x can only be produced from A, and no derivable string
ever has more than one A. So we can have at most one x in any string in L(G).
• zyxzy
Solution: This is in L(G): the unique leftmost derivation is A ⇒ BAB ⇒ zAB ⇒ zBABB ⇒
zyABB⇒ zyxBB⇒ zyxzB⇒ zyxzy.
(b) What is the language of G? You may use regular expression syntax and exponents, e.g., your answer
could be “all strings of the form (xy)nznx∗ for some n≥ 3”.
Solution: By applying the first rule for the start variable A, it can expand into BAB, and repeating this
rule n times yields BnABn. In order to eventually get a string of terminal symbols, we must use the
second rule, expanding the A into x. Since B can expand to either y or z, the strings of terminal symbols
derivable from A are exactly those of the form (y | z)nx(y | z)n for some n≥ 0. These strings form the
language of G.
CSE 103, Fall 2023, Midterm 8
8. (40 pts.) Interpreting a PDA
Consider the following PDA with input alphabet Σ= {0,1} and stack alphabet Γ= {0}:
0,ε → 0
1,ε → ε
0,0→ ε
1,ε → ε
(a) For each of the following words, state whether or not the PDA accepts it (no justification needed).
• ε
Solution: No: all transitions from the start state require reading a symbol, so the PDA would get
stuck and reject.
• 0101
Solution: Yes: we can take the first self-loop to read the first 0 and push it on the stack, then go to
the second state by reading the first 1. We can then read the second 0 and pop the 0 off the stack,
before reading the last 1 to go to the accepting state.
• 0011
Solution: Yes: we can take the self-loop twice to read both 0s and push them on the stack, then
read both 1s to get to the accepting state without modifying the stack further.
(b) What is the language of this PDA?
Solution: We can remain in the start state by reading in 0s, with each one getting pushed onto the
stack. When we read a 1, we must go to the second state (without modifying the stack), whereupon we
can continue to read 0s only as long as there is still a 0 on the stack. We can also read another 1 to go to
the accept state, after which we cannot read any more symbols without getting stuck and so rejecting.
Therefore, we can interpret the first state as counting the number of 0s n which are at the start of the
string before the first 1; then the second state allows us to have up to n more 0s before reading a final
1 and accepting. So the language of the PDA is all strings of the form 0n10m1 with n≥ m≥ 0.