Proposed questions

Download Proposed questions.pdf | View on GitHub

Extracted Content (for search)

Click to view slide text

Theory of Computation 2024F Proposed Questions Compilers: Marina Alchirch & Tashfeen August 25, 2025

Contents 1 Student Proposed Problems for the 1st Assignment 1.1 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.2 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.3 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.4 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.5 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.6 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.7 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.8 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.9 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.10 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.11 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.12 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.13 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.14 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.15 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.16 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.17 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.18 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.19 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.20 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.21 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.22 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.23 Q6: Candidate Exam Question … … … … … … … … … … … . . 1.24 Q6: Candidate Exam Question … … … … … … … … … … … . .

3 3 3 4 4 5 5 6 7 8 8 9 10 11 11 11 12 12 13 13 14 14 15 15 16

2 Student Proposed Problems for the 2nd Assignment 17 2.1 Q6: Candidate Exam Question … … … … … … … … … … … . . 17 2.2 Q6: Candidate Exam Question … … … … … … … … … … … . . 18 2.3 Q6: Candidate Exam Question … … … … … … … … … … … . . 18 2.4 Q6: Candidate Exam Question … … … … … … … … … … … . . 19 2.5 Q6: Candidate Exam Question … … … … … … … … … … … . . 19 2.6 Q6: Candidate Exam Question … … … … … … … … … … … . . 22 2.7 Q6: Candidate Exam Question … … … … … … … … … … … . . 22 2.8 Q6: Candidate Exam Question … … … … … … … … … … … . . 24 2.9 Q6: Candidate Exam Question … … … … … … … … … … … . . 25 2.10 Q6: Candidate Exam Question … … … … … … … … … … … . . 26 2.11 Q6: Candidate Exam Question … … … … … … … … … … … . . 26 1

2.12 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.13 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.14 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.15 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.16 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.17 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.18 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.19 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.20 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.21 NFA Construction … … … … … … … … … … … … … … 2.22 2. DFA using Powerset Construction … … … … … … … … … … . . 2.23 DFA Diagram … … … … … … … … … … … … … … … 2.24 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.25 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.26 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.27 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.28 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.29 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.30 Q6: Candidate Exam Question … … … … … … … … … … … . . 2.31 Q6: Candidate Exam Question … … … … … … … … … … … . .

26 27 28 29 29 30 30 30 31 31 32 33 33 34 34 34 34 35 35 36

3 Student Proposed Problems for the 4th Assignment 37 3.1 Q6: Candidate Exam Question … … … … … … … … … … … . . 37 3.2 Q6: Candidate Exam Question … … … … … … … … … … … . . 38 3.3 Q6: Candidate Exam Question … … … … … … … … … … … . . 39 3.4 Q6: Candidate Exam Question … … … … … … … … … … … . . 39 3.5 Q6: Candidate Exam Question … … … … … … … … … … … . . 40 3.6 Q6: Candidate Exam Question … … … … … … … … … … … . . 41 3.7 Q6: Candidate Exam Question … … … … … … … … … … … . . 42 3.8 Q6: Candidate Exam Question … … … … … … … … … … … . . 42 3.9 Q6: Candidate Exam Question … … … … … … … … … … … . . 44 3.10 Q6: Candidate Exam Question … … … … … … … … … … … . . 44 3.11 Q6: Candidate Exam Question … … … … … … … … … … … . . 45 3.12 Q6: Candidate Exam Question … … … … … … … … … … … . . 45 3.13 Q6: Candidate Exam Question … … … … … … … … … … … . . 46 3.14 Q6: Candidate Exam Question … … … … … … … … … … … . . 46 3.15 Q6: Candidate Exam Question … … … … … … … … … … … . . 47 3.16 Q6: Candidate Exam Question … … … … … … … … … … … . . 48 3.17 Q6: Candidate Exam Question … … … … … … … … … … … . . 48 3.18 Q6: Candidate Exam Question … … … … … … … … … … … . . 48 3.19 Q6: Candidate Exam Question … … … … … … … … … … … . . 49 3.20 Q6: Candidate Exam Question … … … … … … … … … … … . . 50 3.21 Q6: Candidate Exam Question … … … … … … … … … … … . . 50 3.22 Q6: Candidate Exam Question … … … … … … … … … … … . . 51 3.23 Q6: Candidate Exam Question … … … … … … … … … … … . . 52 3.24 Q6: Candidate Exam Question … … … … … … … … … … … . . 53 3.25 Q6: Candidate Exam Question … … … … … … … … … … … . . 53 3.26 Q6: Candidate Exam Question … … … … … … … … … … … . . 54 3.27 Q6: Candidate Exam Question … … … … … … … … … … … . . 54 3.28 Q6: Candidate Exam Question … … … … … … … … … … … . . 55 3.29 Q6: Candidate Exam Question … … … … … … … … … … … . . 55

Student Proposed Problems for the 1st Assignment

1 1.1

Q6: Candidate Exam Question

Draw a DFA recognizing a language L1 = {w|w does not contain the substring 1 0 1 }. Answer: 0

0, 1

1 q1

1.2

Q6: Candidate Exam Question

Explain what language the DFA below recognizes 1

start

1 0

Answer: L1 = {w|w ends with 1}

(1)

1.3

Q6: Candidate Exam Question

Describe the language recognized by the following DFA.

Answer:

1.4

This DFA ”recognizes” the empty language ∅. It has no accept states!

Q6: Candidate Exam Question

Draw a state diagram for a DFA recognizing the language : L = {w | w contains exactly two occurrences of the symbol a}, Σ = {a, b} Answer: b

a start

a,b

b q1

a q2

Explanation: • q0 is the initial state where no a has been encountered. • q1 represents the state where one a has been encountered. • q2 is the accepting state where exactly two a’s have been encountered. • q3 is a dead state for cases where more than two a’s are encountered.

1.5

Q6: Candidate Exam Question

Construct a DFA that recognizes the language L1 = {w | length of w is divisible by 6}, Σ = {0, 1}. Answer: 0,1 start

0,1

q0 0,1

0,1 0,1

0,1

1.6

Q6: Candidate Exam Question

Prove by induction that the sum of the first n odd numbers is equal to n2 . That is, prove the statement: P (n) : 1 + 3 + 5 + … + (2n − 1) = n2 for all natural numbers n ≥ 1. Theorem 1. ∀n ∈ N : 1 + 2 + · · · + n + (n − 1) + · · · + 1 = n2 Answer: Proof. Base Case: For n = 1, the sum of the first odd number is 1. According to the formula, we have: 1 = 12 . Since both sides are equal, the base case holds. Inductive Step: Assume that the statement is true for some k ≥ 1, i.e., assume: 1 + 3 + 5 + … + (2k − 1) = k 2 . We need to show that the statement is true for k + 1, i.e., we need to prove: 1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = (k + 1)2 . Starting from the inductive hypothesis, add the next odd number, 2(k + 1) − 1, to both sides: 1 + 3 + 5 + … + (2k − 1) + (2(k + 1) − 1) = k 2 + (2(k + 1) − 1). Simplify the right-hand side: k 2 + (2(k + 1) − 1) = k 2 + 2k + 2 − 1 = k 2 + 2k + 1 = (k + 1)2 . Thus, the statement holds for k + 1. Conclusion: By the principle of mathematical induction, the statement 1 + 3 + 5 + … + (2n − 1) = n2 is true for all n ≥ 1.

1.7

Q6: Candidate Exam Question

Draw a state diagram for a DFA recognizing the language L = {w | w contains at least two occurrences of 0}, where Σ = {0, 1}. Answer:

The DFA can be represented using the following states and transitions:

start

0,1

• States: – q0 (Initial state, not accepting) – q1 (State with exactly one occurrence of ’0’) – q2 (Accepting state with at least two occurrences of ’0’) • Transitions: – From q0 : ∗ On ’0’, go to q1 ∗ On ’1’, stay in q0 – From q1 : ∗ On ’0’, go to q2 ∗ On ’1’, stay in q1 – From q2 : ∗ On ’0’, stay in q2 ∗ On ’1’, stay in q2 • Start State: q0 • Accepting State: q2

1.8

Q6: Candidate Exam Question 0,1 q1

0 start

1, λ 1 q3

Give a formal description as a 5-tuple for the NFA M5 above. Let Σ = {0, 1}. Answer: M5 = (Q, Σ, δ, q0 , F5 ) Q = {q0 , q1 , q2 , q3 , q4 } Σ = {0, 1} δ is given with: 0 1 δ q0 {q1 } {q3 } q1 {q1 , q2 } {q1 , q3 } q2 {q2 } ∅ ∅ {q4 } q3 q4 ∅ {q4 }

λ ∅ {q3 } ∅ ∅ ∅

q0 is the start state F5 = {q2 , q4 }

1.9

Q6: Candidate Exam Question

List 3 key differences between Nondeterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA). Answer: Here are three key differences between Nondeterministic Finite Automata (NFA) and Deterministic Finite Automata (DFA): • State transitions: DFA: For each state and input symbol, there is exactly one next state. NFA: For each state and input symbol, there can be zero, one, or multiple next states. • Empty string (ε) transitions: DFA: Does not allow ε-transitions (transitions without consuming an input symbol). NFA: Allows ε-transitions, which can move to another state without reading an input. • Computation path: DFA: Has a single unique computation path for any given input string. NFA: Can have multiple possible computation paths for a given input string.

1.10

Q6: Candidate Exam Question

Prove by induction that n! > 2n for n ≥ 4

Answer: Proof. Base Case: let n = 4. Then 4! > 24 ⇒ 24 > 16 Prove: (k + 1)! > 2k+1 Induction: k! > 2k for k ≥ 4 k! > 2k Multiply both sides by (k + 1) (k + 1)k! > (k + 1)2k Simplify both sides (k + 1)k! > (k + 1)2k (k + 1)! > (k)2k + 2k Write a smaller expression with k ≥ 4 (k + 1)! > (k)2k + 2k ≥ (4)2k + 2k Write a smaller expression (k + 1)! > (k)2k + 2k ≥ (4)2k + 2k > (1)2k + 2k Simplify the equation by removing the expressions in between/middle. (k + 1)! > 2k + 2k (k + 1)! > 2k ∗ 2 (k + 1)! > 2k+1

1.11

Q6: Candidate Exam Question

Design a DFA state diagram and the respective 5-tuple for a machine M1 that only accepts strings containing the substring {1111}. Σ = {0, 1} 0 1 start

1 0

q1 0

Answer:

1 q2

1 q3

0 M1 = (Q, Σ, δ, q0 , F )

• The set of states Q is given by: Q = {q0 , q1 , q2 , q3 , q4 } • The alphabet Σ is: Σ = {0, 1} • The transition function δ is defined as: δ(q0 , 0) = δ(q0 , 1) = δ(q1 , 0) = δ(q1 , 1) = δ(q2 , 0) = δ(q2 , 1) = δ(q3 , 0) = δ(q3 , 1) = • The start state q0 is: q0 • The set of accepting (final) states F is: F = {q4 }

q0 q1 q0 q2 q0 q3 q0 q4

0,1

1.12

Q6: Candidate Exam Question

Design a DFA state diagram and the respective 5-tuple for a machine M1 that only accepts strings containing the substring {1111}. Σ = {0, 1} 0 1 start

1 0

q1 0

Answer:

1 q2

1 q3

0 M1 = (Q, Σ, δ, q0 , F )

q0 q1 q0 q2 q0 q3 q0 q4

0,1

1.13

Q6: Candidate Exam Question

Draw a state diagram for a DFA that recognizes the language L = {w | w has an odd number of 0}, Σ{0, 1} Answer:

Figure 1: w with an odd number of 0s

1.14

Q6: Candidate Exam Question

You are given the following parameters of a machine: P • = {0, 1} • L = { w : w begins and ends with the same symbol with total length of at least 2} Properly design the DFA that recognizes such language. Answer:

1 0 q2

0 1

0 1 q4

q5 0

1.15

Q6: Candidate Exam Question

Consider the following finite automaton (FA):

• States: q0 , q1 , q2 • Alphabet: {a, b} • Start State: q0 • Final State: q2 • Transitions: δ(q0 , a) = q1 δ(q1 , a) = q1 δ(q1 , b) = q2 δ(q2 , a) = q2 δ(q2 , b) = q2

What is the language recognized by this automaton? 2. Is the language regular? Provide reasoning based on automata theory. Answer: 1. what is the language recognized by this automaton? The automaton accepts strings over the alphabet {a, b} that contain at least one ’a’ followed by one ’b’. Here’s the reasoning: • In the start state q0 , if the automaton reads ’a’, it moves to q1 . • In q1 , it can read multiple ’a’s and stay in q1 , but as soon as it reads a ’b’, it moves to the final state q2 . • Once the automaton reaches q2 , it stays there, regardless of further input. Therefore, the language recognized is: L = {strings that contain at least one ’a’ followed by one ’b’} or L = {a+ b{a, b}∗ }
Is the Language Regular? Yes, the language is regular. The automaton described is a finite automaton (FA), and it is a fundamental result from automata theory that any language that can be recognized by a finite automaton is regular.

1.16

Q6: Candidate Exam Question

Create the state diagram for DFAs that recognizes the following language: L = w | w must contain 3 consecutive 0’s 1 1 start

1.17

Q6: Candidate Exam Question

Consider the language L for this question: L = {w | w ends with xy, yz, or xz}, Σ = {x, y, z}.

Draw a DFA state diagram for L. 12

2. Provide the formal description of the DFA as a 5-tuple.

Solution

1.18

Q6: Candidate Exam Question

Is this DFA or NFA? Why? 0, 1

0, 1

NFA, q2 has multiple possible transitions.

1.19

Q6: Candidate Exam Question

Let X = {1, 2, 3, 4} and Y = {3, 4, 5, 6}. (i) Is X ∩ Y equal to X ∪ Y ? Justify your answer. (ii) What is (X ∪ Y ) \ (X ∩ Y )? (iii) What is the Cartesian product X × Y ? (iv) Find the powerset of X ∩ Y . Answer (i) X ∩Y = {3, 4} and X ∪Y = {1, 2, 3, 4, 5, 6}. Since X ∩Y ̸= X ∪Y , they are not equal. The intersection X ∩ Y contains only the elements common to both sets, while the union X ∪ Y includes all elements from both sets. 13

(ii) (X ∪ Y ) \ (X ∩ Y ) = {1, 2, 5, 6}. This operation removes the elements that are in both X and Y from their union, leaving only the elements that are unique to each set. (iii) The Cartesian product X × Y is: X×Y = {(1, 3), (1, 4), (1, 5), (1, 6), (2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (3, 5), (3, 6), (4, 3), (4, 4), (4, 5), (4, 6)} (iv) The powerset of X ∩ Y = {3, 4} is: P(X ∩ Y ) = {∅, {3}, {4}, {3, 4}}

1.20

Q6: Candidate Exam Question n+1

−1 (formula for geometric series) for every positive integer n Prove by induction that 1+r +r2 +…+rn = r(r−1)

Solution: n+1 −1 First, verify that 1 + r + r2 + … + rn = r(r−1) is true for n = 1 r2 − 1 (r + 1)(r − 1) r1+1 − 1

= =r+1=1+r r−1 r−1 r−1 Next the inductive step: Assume that 1 + r + r2 + … + rk =

rk+1 − 1 (r − 1)

where k is a positive integer. We show that, 1 + r + r2 + … + rk + rk+1 =

r(k+1)+1 − 1 (r − 1)

Based on our previous assumption, we observe that rk+1 − 1

rk+1 (r − 1) rk+1 − 1 + rk+1 (r − 1) = r−1 rk+1 − 1 + rk+2 − rk+1 = r−1 k+2 r −1 = r−1 r(k+1)+1 − 1 = r−1

1 + r + r2 + … + rk + rk+1 =

n+1

−1 By the Principle of Mathematical Induction, it follows that 1 + r + r2 + … + rn = r(r−1) for every positive integer n QED

1.21

Q6: Candidate Exam Question

Let A be the set {x, y, z} Is the empty set ∅ an element of A? What about the power set P(A) of A? Answer The empty set is not an element of A, but it is an element of the power set of A. −→ P

1.22

Q6: Candidate Exam Question

Problem: Let set A = {2, 4, 6, 8} and A \ B = {4, 6}. (a) If set B has two elements, what is set B? (b) What is A ∪ B? (c) What is A ∩ B? (d) What is A × B? (e What is the powerset of A?

Solution: (a) Since A \ B = {4, 6}, the elements of B must be the elements of A that are not in A \ B. B = {2, 8} (b) A ∪ B is the set of elements in either A or B, that do not repeat. A ∪ B = {2, 4, 6, 8} (c) A ∩ B is the set of elements that are in both A and B. Since B = {2, 8} and A = {2, 4, 6, 8}, we have A ∩ B = {2, 8}. (d) A × B is the set of ordered pairs where the first element is from A and the second is from B. So, A × B = {(2, 2), (2, 8), (4, 2), (4, 8), (6, 2), (6, 8), (8, 2), (8, 8)}. (e) The power set of A, P(A), is the set of all subsets of A. So, P(A) = {∅, {2}, {4}, {6}, {8}, {2, 4}, {2, 6}, {2, 8}, {4, 6}, {4, 8}, {6, 8}, {2, 4, 6}, {2, 4, 8}, {2, 6, 8}, {4, 6, 8}, {2, 4, 6, 8}}.

1.23

Q6: Candidate Exam Question

Question: Draw the state diagram for a DFA which recognizes the following language: L = {w | w begins and ends with the same symbol}, Σ = {a, b}. Possible Solution:

a q1

q3 b

a q0

start

b b q2

q4 a

1.24

Q6: Candidate Exam Question

Problem: For the language construct a DFA L1 ={w| The sub string abba must occur at least once}. Solution: See DFA below. q4 is accepting zoom in to see state better.

a a

Student Proposed Problems for the 2nd Assignment

2 2.1

Q6: Candidate Exam Question

Use the Pumping Lemma method to prove that the following language is not regular: L = {as bq ar |r = s + q} Answer: Proof. Let’s assume that L is regular; based on the Pumping Lemma, there’s some constant p where the size of an accepted input S is at least p (in other words, S ∈ L, |S| ≥ p), and that S can be represented as xyz such that: • |xy| ≤ p, • |y| > 0, and • xy i z ∈ L. • As an example, let’s consider the accepted string S ′ = ap bap+1 , where |S ′ | = 2p + 2 ≥ p. Since |xy| cannot be greater than p, then: – x = aα , α ≥ 0, – y = aβ , β ≥ 1, and – z = ap−α−β bap+1 , where α + β ≤ p. xy i z = aα aiβ ap−α−β bap+1 = ap+iβ−β bap+1 • However, we notice that, when setting i = 2: xy 2 z = ap+2β−β bap+1 = ap+β bap+1 which is not included in L because: p + 1 ̸= p + β + 1 since β cannot be less than 1. • Thus, with proof by contradiction, L is not considered regular.

2.2

Q6: Candidate Exam Question

Let Σ = {0, 1}. Give regular expressions for the following languages:

L1 = {w | w contains an even number of 1s}.
L2 = {w | w starts and ends with the substring ’01’}. Answer:
The regular expression containing an even number of 1s can be shown as: L1 = (0∗ (10∗ 10∗ )∗ ) Explanation: Where you pair 1 with another 1, allowing any number of 0s between.
The regular expression that starts and ends with the substring ’01’ can be shown as: L2 = 01(0 | 1)∗ 01 Explanation: Where we can observe the string beginning with 01, followed by a combination of 0s and/or 1s and ending with 01.

2.3

Q6: Candidate Exam Question

Let Σ = {a, b, c}. Consider the following language: L = {w|w contains no more than one c and ends with abc} a) Rewrite L as a regular expression. b) Draw a state diagram representing L.

Answer: b)

a) (a + b)∗ abc

a, b, c

5 c

4 c

b a

2.4

Q6: Candidate Exam Question

Design an NFA for the regular expression: R= (a|b)∗ a(a|b)a

Answer:

2.5

Q6: Candidate Exam Question

Consider the Non-deterministic Finite Automaton (NFA) for this question:

Convert the NFA to DFA.
Using your DFA convert it to a regular expression.

Answer:

2.6

Q6: Candidate Exam Question

Let Σ = {0, 1}. Give regular expressions for the following languages. (i) L1 = {w | w contains at most three 1s}. (ii) L2 = {w | w contains exactly two 0s}. Answer: (i) 0∗ + (0∗ )1(0∗ ) + (0∗ )1(0∗ )1(0∗ ) + (0∗ )1(0∗ )1(0∗ )1(0∗ ) (ii) (1∗ )0(1∗ )0(1∗ )

2.7

Q6: Candidate Exam Question

Convert the given NFA to a regular expression using the node deletion method. q2 1 1 1 start

Answer:

Normalize

q2 1 1 start

1 2. Rip q3 and redraw q1 . q2 1 1 start

01*0

F 3. Rip q1 and redraw q0 to q2 . 1+0(01*0)*1 start

q2 1

F 4. Rip q2 and redraw q0 . (1+0(01*0)*1)1

start

5. Rip q0 and redraw S to F. ((1+0(01*0)1)1) start

F REGEX: ((1+0(01*0)1)1)

2.8

Q6: Candidate Exam Question

Let Σ = {a, b}. Give regular expressions for the following languages:

L1 = {w | w contains at least two a’s and at least one b}.
L2 = {w | w ends with the substring aba}. Answer:
Language L1 = {w | w contains at least two a’s and at least one b} : L1 : (a + b)∗ a(a + b)∗ a(a + b)∗ b(a + b)∗ Explanation: • The first (a + b)∗ - combination of ’a’s and ’b’s before the first ’a’. • The first a - ensures the first required ’a’. Same with the second a. • The second (a + b)∗ - combination of ’a’s and ’b’s between the first and second ’a’. • The next (a + b)∗ b(a + b)∗ - there is at least one ’b’ somewhere in the string, with combination of ’a’s and ’b’s before or after the ’b’.
Language L2 = {w | w ends with the substring aba} : L2 : (a + b)∗ aba Explanation: • The first (a + b)∗ - combination of ’a’s and ’b’s before the substring ”aba”. • The substring ”aba” ensures the string ends with the required substring.

2.9

Q6: Candidate Exam Question

Let Σ = {0, 1}. Provide regular expressions for the following languages: (i) L1 = {w | w contains the substring 001}. (ii) L2 = {w | w does not contain the substring 11}. (iii) L3 = {w | w contains at least three 1s and at least two 0s}. Answer: (i) The regular expression for L1 is:

L1 = (0 + 1)∗ 001(0 + 1)∗

This regular expression ensures that the string contains the substring ”001” somewhere, with any sequence of 0s and 1s before and after it. (ii) The regular expression for L2 is:

L2 = (0 + 10)∗

This ensures that no two consecutive 1s appear in the string. The pattern allows any combination of 0s and single 1s. (iii) The regular expression for L3 is: L3 = (0 + 1)∗ 1(0 + 1)∗ 1(0 + 1)∗ 1(0 + 1)∗ 0(0 + 1)∗ 0(0 + 1)∗ This regular expression ensures that the string contains at least three occurrences of 1 and at least two occurrences of 0, with any combination of 0s and 1s before, between, and after them.

2.10

Q6: Candidate Exam Question

Draw the NFA of the language: L = {w | w contains the substring 101} Answer:

2.11

Q6: Candidate Exam Question

Give an NFA for the language L = {w|w contains 101 or w contains 111}. Answer 0, 1

0, 1

1 q5

2.12

Q6: Candidate Exam Question 0

start

0 1

Convert this NFA into a GNFA

Answer: 0

start

0 1

0, 1 θ

0, 1 0

start

0 1

start

0 1

start

2.13

λ 0101

10*1

Q6: Candidate Exam Question

i) Convert the following NFA to a DFA using powerset construction and write it out as a 5-tuple.

ii) The equivalent DFA needs only one state, not 16. Explain why. Answer i) The NFA is M = (Q, Σ, δ, q0 , F ) where Q = q0 , q1 , q2 , q3 , Σ = ∅, and F = q2 . The equivalent DFA is M ′ = (Q′ , Σ, δ ′ , r0 , F ′ ) where: • Q′ = P (Q) = {∅, {q0 }, {q1 }, {q2 }, {q3 }, {q0 , q1 }, {q0 , q2 }, {q0 , q3 }, {q1 , q2 }, {q1 , q3 }, {q2 , q3 }, {q0 , q1 , q2 }, {q0 , q1 , q3 }, {q0 , q2 ( ∅ R=∅ ′ • δ (R, a) = {q ∈ Q|q ∈ Λ(δ(r, a)) for some r} = {q0 , q1 , q2 , q3 } R ̸= ∅ • r0 = Λ(q0 ) = {q0 , q1 , q2 , q3 } • F ′ = {R ∈ Q′ |R∩F ̸= ∅} = {{q2 }, {q0 , q2 }, {q1 , q2 }, {q2 , q3 }, {q0 , q1 , q2 }, {q0 , q2 , q3 }, {q1 , q2 , q3 }, {q0 , q1 , q2 , q3 }} ii) None of the DFA’s states other than q0 , q1 , q2 , q3 are reachable. It starts at q0 , q1 , q2 , q3 , and the ”transition” function keeps it at q0 , q1 , q2 , q3 (in fact the transition function can’t even be actually invoked because Σ = ∅). 27

2.14

Q6: Candidate Exam Question

Let Σ = {0, 1}. Consider the language L = {w | w contains at least two consecutive 1s}.

(i) [4 points] Construct a regular expression for the language L.
(ii) [6 points] Design an NFA that recognizes the language L.
(iii) [8 points] Use the powerset construction to convert your NFA from part (ii) into an equivalent DFA. Answer To create a regular expression for L, which consists of strings that contain at least two consecutive 1s, we can describe the solution in the following way: • Any string of 0s or 1s can precede the first occurrence of the two consecutive 1s. • After these two consecutive 1s appear, any number of 0s or 1s can follow. Thus, the regular expression is: (0 | 1)∗ 11(0 | 1)∗ NFA that recognizes the language L = {w — w contains at least two consecutive 1s}.

0 q0

start

0,1

We convert the NFA from part (ii) to a DFA using the powerset construction method. The set of states for the NFA is {q0 , q1 , q2 }. The powerset of these states is: P (Q) = {∅, {q0 }, {q1 }, {q2 }, {q0 , q1 }, {q1 , q2 }, {q0 , q1 , q2 }} The powerset construction method yields the following DFA: • States: – {q0}: Initial state, no 1s seen yet – {q0,q1}: One 1 has been seen – {q0,q1,q2}: At least two consecutive 1s have been seen (accepting state) • Transitions: – From {q0}: ∗ On 0: Stay in {q0} ∗ On 1: Move to {q0,q1} – From {q0,q1}: ∗ On 0: Move back to {q0} ∗ On 1: Move to {q0,q1,q2} (accepting state) – From {q0,q1,q2}: ∗ On 0: Stay in {q0,q1,q2} ∗ On 1: Stay in {q0,q1,q2}

DFA Diagram

0,1 0

{q0 }

start

{q0 , q1 }

{q0 , q1 , q2 }

0 2.15

Q6: Candidate Exam Question

a) Consider the string x = ap bap bap b in L1 (where w = ap b). Assume that L1 is regular. By the Pumping Lemma, we can pump on the prefix ap of x. Thus, ap can be written as ap = ai ak aj , where i + k + j = p and k > 0. This allows us to express the string as: xr = ai (ak )r aj bap bap b = ai ark aj bap bap b which is in the language L1 for all r > 0. However, if we let r = 2p + 2 (with k > 0), the string x2p+2 = ai a2pk+2k aj bap bap b cannot be of the form www for any w ∈ {a, b}∗ , and hence cannot be in the language L1 . This contradiction proves that the language L1 is not regular.

2.16

Q6: Candidate Exam Question

Let Σ = {0, 1}. Find a regular expression for the language: L3 = {w | w has an even number of 1s}. The regular expression for this language is: L3 = (0∗ (10∗ 1))∗ 0∗ Explanation: • 0∗ allows any number of 0s (including none) between or around the 1s. • 10∗ 1 ensures that each block of 1s contains exactly two 1s. • (0∗ (10∗ 1))∗ repeats this pattern of alternating between blocks with two 1s and any number of 0s. • The final 0∗ allows the string to end with any number of 0s without affecting the count of 1s. This regular expression captures all strings containing an even number of 1s, while allowing any amount of 0s in between.

2.17

Q6: Candidate Exam Question

What is the difference between a Deterministic Finite Accepter (DFA) and a Nondeterministic Finite Accepter (NFA)? Solution:

A Deterministic Finite Accepter (DFA) has exactly one transition for each symbol in the input alphabet from any given state. This means that for each input, the DFA can only be in one state at any point in time.
A Nondeterministic Finite Accepter (NFA), on the other hand, allows multiple transitions for a given input symbol and state. An NFA can be in several possible states at once, and it can even have transitions that do not consume any input symbols (ε-transitions).

2.18

Q6: Candidate Exam Question

Show that the following is not a regular language: F = {an bn cn | n ≥ 1} Answer: We will use the Pumping Lemma for regular languages to prove that F is not regular. Proof: Towards contradiction, by assuming that F is a regular language with pumping length p. The Pumping Lemma says that if F is a regular language, then there is a pumping length p, where, if any string s ∈ F and is also |s| ≥ p, then s may be divided into three pieces, s = xyz where:

|xy| ≤ p
|y| > 0
xy i z ∈ A, for every i ∈ {0, 1, 2, 3…} The string we will use is s = ap bp cp . This has a length |s| = 3p ≥ p. From property 1, |xy| ≤ p, so x and y can only consist of a’s. So since y is only made up of a’s, y = al , which means l > 0. We pump the string now by setting i = 2 (from property 3) which gives us: xy 2 z = xyyz = ap+l bp cp This new string is not in F anymore because the number of a’s is not equal to the number of b’s and c’s which is required in order to be a valid string in F . Therefore, we have a contradiction.

2.19

Q6: Candidate Exam Question

Question: Consider the NFA given below with states Q = {q1, q2}, and transitions as: • From q1 to q2 on input 0, • From q1 to q1 or q2 on input 1, • From q2 to q2 on input 0. Convert this NFA to a DFA using the powerset construction, and provide the resulting DFA. Solution: To apply the powerset construction:

The NFA has two states, Q = {q1, q2}. The powerset of Q is P (Q) = {∅, {q1}, {q2}, {q1, q2}}.
Start by labeling the DFA states as corresponding subsets of Q. The new DFA states are ∅, {q1}, {q2}, {q1, q2}.

3. For each input 0 and 1, calculate the transitions: • From state {q1}: 0

– On input 0, the NFA transitions to q2, so {q1} − → {q2}. 1

– On input 1, the NFA transitions to both q1 and q2, so {q1} − → {q1, q2}. • From state {q2}: 0

– On input 0, the NFA stays in q2, so {q2} − → {q2}. – On input 1, there is no transition defined, so it goes to ∅. • From state {q1, q2}: 0

– On input 0, the NFA transitions to q2, so {q1, q2} − → {q2}. 1

– On input 1, the NFA transitions to q1 and q2, so {q1, q2} − → {q1, q2}. • From state ∅: – On both inputs, it remains in ∅. 4. The DFA has four states: ∅, {q1}, {q2}, {q1, q2}. The initial state is {q1}, and the accepting states depend on the accepting state in the NFA. DFA Diagram: 1

0 0

start

{q1}

{q2} 1

0 {q1, q2}

∅

0,1 1

2.20

Q6: Candidate Exam Question

Let the language L be defined as: L = {w | w is a binary string that ends with 10 or 01}. The alphabet of the language is Σ = {0, 1}.

Draw an NFA for the above language.
Convert the NFA into DFA using Powerset construction.

2.21

NFA Construction

The NFA for the language L is defined as follows: • States: Q = {q0 , q1 , q2 , q3 , q4 } • Alphabet: Σ = {0, 1} 31

• Start state: q0 • Accept states: F = {q2 , q4 } • Transition function δ: NFA Diagram 0,1

start

2.22

DFA using Powerset Construction

Using the powerset construction, we derive the following DFA states: • DFA States: – S0 = {q0 } (Start state) – S1 = {q0 , q1 } – S2 = {q0 , q3 } – S3 = {q0 , q2 , q3 } (Accepting state) – S4 = {q0 , q1 , q4 } (Accepting state) • Transition Table: DFA State S0 = {q0 } S1 = {q0 , q1 } S2 = {q0 , q3 } S3 = {q0 , q2 , q3 } S4 = {q0 , q1 , q4 }

0 S5 = {q0 , q3 } S3 = {q0 , q2 , q3 } S2 = {q0 , q3 } (no transition) (no transition)

1 S6 = {q0 , q1 } S1 = {q0 , q1 } S4 = {q0 , q1 , q4 } (no transition) (no transition)

2.23

DFA Diagram start

S4 The final accepting states in the DFA will correspond to the sets containing q2 or q4 .

2.24

Q6: Candidate Exam Question

Show that the following Language is not regular: L = {w ϵ {0,1}* : w has same number of 0’s and 1’s} i.e 0011, 0101, 1001 Solution: Proof by Contradiction of Closure Property.

Assume L is regular.
If L is regular, L should be closed under intersection of another regular language (regex).
L’ = L ∩ 01 (regex) = {0n 1n : n ≥ 0} (a) Assume L’ is regular. (b) Assume ∃ p (pumping constant) for L’. (c) Choose w = 0p 1p . (d) Decompose w into XYZ s.t. i. |XY | ≤ p ii. |Y | ≥ 1 A. X = 0α , α ≥ 0, α + β ≤ p B. Y = 0β , β ≥ 1 C. Z = 0p−α−β 1p (e) Choose i s.t. XY i Z ̸ ϵ L′ i

i. XY i Z = 0α 0β 0p−α−β 1p ii. XY i Z = 0p+iβ−β 1p iii. p + iβ − β ̸= p, (remove p) iv. iβ − β ̸= 0, (plus β) v. iβ ̸= β, (divide β) vi. i ̸= 1 vii. When i is any value other than 1, L’ is not regular due to proof by contradiction via the Pumping Lemma Theorem. 4. Since L’ which was generated from L ∩ 0∗ 1∗ is proven to not be regular, L is shown to not be regular. 33

2.25

Q6: Candidate Exam Question

Let Σ = {a, b, c}. Give regular expressions for the following language.

L1 = {w|w contains at least three a’s and ends with two b’s, or contains the substring cabab.}. Σ∗ aΣ∗ aΣ∗ aΣ∗ bb + Σ∗ cababΣ∗
L2 = {w|w contains any arrangement of a or b, or only contains c’s and has length 12.}. (a + b)∗ + c12

2.26

Q6: Candidate Exam Question

How many steps are required in order to convert the following DFA into a regular expression? Explain Each step. a

start

1 b 2

a, b

Create a start and accept state with λ transitions.
Remove state 2, connecting state 1 with the accept state with the expression b(a + b)∗ .
Remove state 1, connecting the start state with the accept state with the expression becoming (a)∗ b(a+ b)∗ .

2.27

Q6: Candidate Exam Question

Let Σ = {a, b, c, d}. Give the regular expression for the following language. L = {w | w starts with a, contains substring bb, ends with substring ccc.} Solution: a(a + b + c + d)∗ bb(a + b + c + d)∗ ccc The question is simple and aims to challenge the preciseness of the answers. Intuitively you would think abbccc would be the answer however you would need to take in account of the characters between a and bb as well as bb and ccc.

2.28

Q6: Candidate Exam Question

Let Σ = {0, 1}.State the Pumping Lemma theorem and that knowledge to prove thelanguage below is not regular. L = {0m 10n | m, n ≥ 0, m = n or m = 2n} Proposed Answer By their of the pumping lemma, we have the pumping length of p and s as a string. s = xyz Three cases need to satisfy the condition to prove L is not regular: |y| > 0

|xy| ≤ p for every k ≥ 0, xy i z ∈ L We first assume L is regular for later proving contradiction. there exist p so that |w| ≥ p. we can choose string 0p−m 102p 1. First, we consider y= 0m where 0 < m ≤ p and |xy| ≤ p.This will keep |xy| ≤ p This means that y must have multiple input strings of 0. Finally, we choose string xy i z = 0p−m 102p 1. The string in L has a length of 3p+1, which is greater than p. Such string cannot be in L because the first series of 0 followed by 1 will have another set of different is no longer have the same length as the second series of 0 after 1. Double the amount of the series of 0 after 1 is also not in L. This a contradiction because there exist a string in L that cannot be pumped for any pumping length p. As a result, the language is not regular.

2.29

Q6: Candidate Exam Question

Let Σ = {0, 1}. Give regular expressions for the following languages. (i) La = {w | w contains at least two 1s}. Answer: (0 + 1)∗ 1(0 + 1)∗ 1(0 + 1)∗ (ii) Lb = {w | w starts and ends with the same symbol}. Answer: (0 + 1) + (0(0 + 1)∗ 0) + (1(0 + 1)∗ 1)

2.30

Q6: Candidate Exam Question

Convert the following DFA to its equivalent regular expression. 1

1 0

start

1 0

Where Σ = {0, 1} represented by the language L = {w|w starts with 0 or 1, contains at least two 0’s, and ends with 0}.

(i) Create Regular Expression on q0 . From q0 to q1 , there is a 0. On q0 there exists a self-loop for a 1 for any amount of 1’s. Thus, to get from q0 to q1 , we get the following regular expression. 1∗0 (ii) Create Regular Expression on q1 . From q1 to q2 there is a 0. On q1 there exists a self-loop for a 1 for any amount of 1’s. Thus, to get from q0 to q2 , we get the following regular expression. 1 ∗ 0(1∗)0 (iii) Create Regular Expression on q2 . From q2 to q3 , there is a 0. On q2 there exists a self-loop for a 1 for any amount of 1’s. Thus, to get from q0 to q3 , we get the following regular expression. (1∗)0(1∗)0(1∗)0

2.31

Q6: Candidate Exam Question

Q: Create an NFA state diagram that: L1 = {w | w ends with two 1}. 0

start λ

End

Student Proposed Problems for the 4th Assignment

3 3.1

Q6: Candidate Exam Question 2

Prove that L = {an : n ≥ 0} is not a context-free language.

Answer: 2

Proof. Towards contradiction, assume L is a CFL with pumping length p. Let us look at the string s = ap . As |s| = p2 ≥ p , we can apply the pumping lemma for CFLs. This means that s = uvxyz s.t. 1. for each i ≥ 0, uv i xy i z ∈ L 2. |vy| > 0 3. |vxy| ≤ p Let us pump up with i = 2. Thus, we are looking at s′ = uv 2 xy 2 z. Therefore, |s′ | = |uvxyz| + |vy| 2

= p + |vy| > p

(2) (3)

Let |vxy| = k ≤ p. Thus, |vy| = k − |x| ≤ k ≤ p as x can be the empty string. Therefore, |s′ | ≤ p2 + p = p(p + 1) 2

′

p < |s | ≤ p(p + 1)

(4) (5)

The next perfect square after p2 is (p + 1)2 . However, p(p + 1) < (p + 1)2 . Thus, p2 < |s′ | < (p + 1)2

(6)

Since |s′ | is within the interval of two consecutive perfect squares, non-inclusive, its length cannot be a perfect square. Therefore, s′ ∈ / L, meaning L cannot be context-free.

3.2

Q6: Candidate Exam Question

Show that the following language is not context-free.

L = {w ∈ {0, 1, 2}∗ | w has an equal number of 0’s, 1’s, and 2’s} Answer: Proof. To prove L is not context-free, we need to use the pumping lemma for context-free languages. We first apply the pumping lemma by assuming that L is context-free. Then, there must exist a pumping length p such that any string s ∈ L with |s| ≥ p can be decomposed as s = uvxyz with the following conditions: • For each i ≥ 0, uv i xy i z ∈ L, • |vy| > 0, • |vxy| ≤ p. A string is constructed that satisfies the condition of having equal numbers of 0’s, 1’s, and 2’s, and has a length at least p: In this case, let s = 0p 1p 2p , where each symbol has length p and is contained in L.

Using the pumping lemma, s is split into s = uvxyz where the conditions |vxy| ≤ p and |vy| > 0 hold. The substring vxy can contain at most two types of symbols because its length is at most p. In this proof, we consider two cases for v and y:

The first case covers v and y containing only one type of symbol, where the symbols either contain only 0’s, 1’s, or 2’s. Then, pumping v and y would increase the count of those symbols without affecting the counts of the other symbols, leading to an unequal number of 0’s, 1’s, and 2’s, which is not contained in L.
The second case covers v and y containing two different symbols. For example, let v contain 0’s and y contain 1’s. Pumping v and y would lead to an unequal number of 0’s and 1’s as well as an unequal number of 2’s, which is also not contained in L. We have shown in both cases that there is a contradiction with pumping s, since it would lead to an unequal number of 0’s, 1’s, and 2’s, which is not contained in L. Thus, we have proven that L is not context-free.

3.3

Q6: Candidate Exam Question

Show that L = {an bm | m = n2 } is not context-free. Answer: 2

Proof. Using the pumping lemma, assume the contrary, and let s = uvxyz = ap bp . The lemma says uv i xy i z ∈ L for any i ≥ 0. Clearly, if either v or y straddles the boundary between a’s and b’s, pumping s 2 will generate strings not in L. If v and y are composed entirely of a’s, then uv 2 xy 2 z = ap+j bp , 0 < j ≤ p, which is not in L since the number of b’s is no longer the square of the number of a’s. The same argument holds if vy = bk . The only remaining case is when v is one or more a’s and y is one or more b’s. If this is the 2 case, then we have uv 2 xy 2 z = ap+j bp +k , where j, k > 0. But p2 + k < (p + 1)2 since (p + 1)2 = p2 + 2p + 1 and k < p (because k + j ≤ p). Since p2 + k cannot be any perfect square, it certainly cannot be (p + j)2 for any j > 0. Since every case results in a contradiction, L is not context-free.

3.4

Q6: Candidate Exam Question

Design a PDA recognizing the language L5 Let L5 be the language defined as: L5 : A = {w ∈ {0, 1}∗ | w contains at least three 1s}

Figure 2: PDA representing L5

Answer:

3.5

Q6: Candidate Exam Question

Consider the Context-Free Grammar (CFG) for this question: S → aXbX X → XaXb | XbXa |λ • What Language does the CFG accept? • Convert the CFG to PDA Answer: • The CFG accepts the language where number of a’s = number of b’s CFG to PDA below:

3.6

Q6: Candidate Exam Question

Convert the following context-free grammar into Chomsky Normal Form (CNF). The grammar is defined as follows: S → AB | CA A → aA | B | a B → bB | C | b C → AB | ϵ

Answer: Step 1 Add New Start Variable: ⟨S0 ⟩ → S S → AB | CA A → aA | B | a B → bB | C | b C → AB | ε Step 2 Remove All ε Rules: ⟨S0 ⟩ → S | ε S → AB | CA | A | B | C A → aA | B | a B → bB | C | b C → AB | A | B Step 3 Remove All Unit Rules: ⟨S0 ⟩ → ε | AB | CA | aA | a | bB | b S → AB | CA | aA | a | bB | b A → aA | a | bB | b | AB B → bB | b | AB C → AB Step 4 Chomsky Normal Form ⟨S0 ⟩ → ε | AB | CA | a | b | ⟨Z1 ⟩A | ⟨Z2 ⟩B S → AB | CA | a | b | ⟨Z1 ⟩A | ⟨Z2 ⟩B A → a | b | AB | ⟨Z1 ⟩A | ⟨Z2 ⟩B B → b | AB | ⟨Z2 ⟩B C → AB ⟨Z1 ⟩ → a ⟨Z2 ⟩ → b

3.7

Q6: Candidate Exam Question

Construct a PDA from the given language {An B n | n ≥ 0},

= {A, B}

Answer: A, λ → A

start

3.8

λ, λ → $

B, A → λ λ, λ → λ

λ, $ → λ

Q6: Candidate Exam Question

Consider the language L = {0m 1n | m ̸= n} over the alphabet Σ = {0, 1}.

Show that L is not a context-free language using the Pumping Lemma for context-free languages.
If L were modified to include strings where m ≤ n (i.e., L′ = {0m 1n | m ≤ n}), would L′ be recognized by a Pushdown Automaton? Provide a brief justification for your answer. Answer: Part 1: Showing L = {0m 1n | m ̸= n} is Not Context-Free To show that L is not context-free, we’ll use the Pumping Lemma for context-free languages, which provides a way to demonstrate that certain languages are not context-free by finding contradictions when ”pumping” portions of strings within the language.
Assume L is Context-Free: We start by assuming, for contradiction, that L is a context-free language. According to the Pumping Lemma, there exists a pumping length p such that any string s in L with |s| ≥ p can be split into five parts, s = uvwxy, with specific properties: • |vwx| ≤ p (the ”pumped” portion is limited in length), • |vx| > 0 (the pumped section is non-empty), • For any i ≥ 0, uv i wxi y ∈ L.
Choosing a String s in L: Let’s select a string s = 0p 1p+1 in L. This string has m = p occurrences of 0 and n = p + 1 occurrences of 1, so m ̸= n, meaning s ∈ L. The length |s| = p + (p + 1) = 2p + 1, which satisfies |s| ≥ p.
Applying the Pumping Lemma: According to the Pumping Lemma, we can split s = uvwxy with |vwx| ≤ p and |vx| > 0. Since |vwx| ≤ p, the substring vwx consists only of 0s (it’s in the first p characters of s, which are all 0s). This means that v and x only contain 0s, so pumping v and x (repeating them) will only add more 0s to the string.
Pumping v and x: If we increase the number of 0s by choosing i = 2, the resulting string becomes uv 2 wx2 y, which has more than p 0s. Specifically, it now has more than p + 1 0s, making m ≥ n, which contradicts the original property m ̸= n for strings in L. Thus, uv 2 wx2 y ∈ / L, as the pumped string does not satisfy the language condition m ̸= n.
Conclusion: Since pumping v and x leads to a string that is not in L, this contradicts the Pumping Lemma. Therefore, L is not a context-free language.

Part 2: Determining if L′ = {0m 1n | m ≤ n} is Recognizable by a PDA In this part, we consider a modified version of the language L, where we allow strings with equal or more 1s than 0s. We’ll see if this modified language L′ can be recognized by a Pushdown Automaton (PDA).

Understanding the Language L′ : The language L′ = {0m 1n | m ≤ n} includes all strings where the number of 0s is less than or equal to the number of 1s. This means strings like 02 13 (where m = 2 and n = 3) and 03 13 (where m = n = 3) are included, but strings like 04 13 are not, as they have more 0s than 1s.
Constructing a PDA for L′ : A PDA can recognize a language like L′ by using its stack to count the number of 0s and 1s: • The PDA starts by pushing a symbol onto the stack for each 0 it reads. • When it begins reading 1s, it pops a symbol from the stack for each 1. • If there are more 1s than 0s (i.e., the stack becomes empty while still reading 1s), the PDA can continue to accept these additional 1s without needing to push any more symbols. • If the PDA encounters an unmatched 0 (meaning more 0s than 1s by the end), it will reject.
Justification: The PDA can recognize L′ because it only needs to keep track of the difference between the number of 0s and 1s. Since a PDA can push and pop symbols to handle counting and comparison, it is well-suited for this task. The PDA can accept any string where the number of 0s is less than or equal to the number of 1s.
Conclusion: Yes, L′ can be recognized by a PDA, as the stack allows the PDA to compare the counts of 0s and 1s. The PDA will accept strings with m ≤ n by correctly balancing pushes and pops on the stack, making this language context-free.

3.9

Q6: Candidate Exam Question

Given the Turing machine diagram below, write the Turing machine configuration that describes it.

Answer:

3.10

Configuration: 10a0aq7 $10a0a

Q6: Candidate Exam Question

Using the construction from class, construct a PDA that accepts the language L1 defined by the grammar: S −→ aSb | bSa | λ Answer:

The solution to this problem is shown in the figure below.

Figure 3: Solution to PDA Construction Problem

3.11

Q6: Candidate Exam Question

Answer with True or False and explain your answer: The language L = {0n 1n | n ≥ 1} can be recognized by a deterministic finite automaton (DFA). Answer: False. The language L = {0n 1n | n ≥ 1} needs memory to match the number of 0s with the number of 1s. This means that a deterministic finite automaton cannot handle recognize it because of its limited state-based memory. In order to recognize this language, we would need a pushdown automaton because it has access to a stack.

3.12

Q6: Candidate Exam Question

Let L be the language defined as: L = {an bn cn | n ≥ 0} where a, b, and c are symbols in the alphabet Σ = {a, b, c}. Using the Pumping Lemma for context-free languages, prove that L is not a context-free language. Answer: To prove that L is not context-free, use the following steps based on the Pumping Lemma for context-free languages:

Assume that L is context-free.
By the Pumping Lemma, there exists a pumping length p such that any string s ∈ L with |s| ≥ p can be written as s = uvwxy with: • |vwx| ≤ p, • |vx| ≥ 1, and • For all k ≥ 0, uv k wxk y ∈ L.
Choose a string s ∈ L that satisfies |s| ≥ p. Choose s = ap bp cp .
Show that for any decomposition of s as uvwxy that meets the conditions above, pumping v and x will produce a string that is not in L. This will lead to a contradiction, proving that L is not context-free. Proof. 1. Assume that L is context-free. Then, by the Pumping Lemma for context-free languages, there exists a pumping length p such that any string s ∈ L with |s| ≥ p can be written as s = uvwxy with |vwx| ≤ p, |vx| ≥ 1, and for all k ≥ 0, uv k wxk y ∈ L.
s = ap bp cp , which is a string in L with |s| ≥ p. Since |vwx| ≤ p, the substring vwx can contain symbols from at most two of the three groups of symbols a, b, or c, because vwx is confined to a length of p. This implies that either v and x contain only a’s, only b’s, or only c’s, or they contain a combination of two of these symbols but not all three. Consider the cases: Case 1. If v and x contain only a’s and/or b’s, pumping s (i.e., increasing k in uv k wxk y) will change the number of a’s and/or b’s without affecting the number of c’s. then the resulting string will not have equal numbers of a’s, b’s, and c’s and will therefore not belong to L. Case 2. If v and x contain only b’s and/or c’s, pumping s will alter the number of b’s and/or c’s without affecting the number of a’s, resulting in a string that is also not in L. In all cases, pumping v and x leads to a contradiction, it produces strings that do not belong L. Therefore, L does not satisfy the Pumping Lemma for context-free languages, so L is not a context-free language.

3.13

Q6: Candidate Exam Question

Create a PDA that recognizes the language L: L = {w ∈ {a, b}∗ : a = b } Answer:

3.14

Q6: Candidate Exam Question

Construct a pushdown automata that accepts the language L1 defined by the grammar: S → 0|1U 0 U → SU S|λ Answer

λ, λ → U start λ, λ → $

λ, S → 0 λ, λ → 1

λ, λ → $ λ, S → 0 λ, U → λ 0, 0 → λ 1, 1 → λ

loop

λ, U → S

λ, λ → U

λ, λ → S

λ, $ → λ

f in

3.15

Q6: Candidate Exam Question

Proof that L2 = {1n | n is prime} is Not Context-Free To prove that L2 is not context-free, we will use the pumping lemma for context-free languages. The pumping lemma states that for any context-free language L, there exists a constant p (the pumping length) such that any string s in L of length at least p can be decomposed into five parts s = uvwxy satisfying the following conditions:

|vwx| ≤ p
|vx| ≥ 1
For all i ≥ 0, the string uv i wxi y ∈ L. Step 1: Assume L2 is context-free Assume, for the sake of contradiction, that L2 is context-free. By the pumping lemma, there exists a pumping length p. Step 2: Choose a string s Let us choose the string s = 1q , where q is a prime number greater than p. Clearly, s ∈ L2 because q is prime. Step 3: Decompose s According to the pumping lemma, we can write s = uvwxy such that: • |vwx| ≤ p • |vx| ≥ 1 Since |vwx| ≤ p and p < q, the segments v and x can only consist of 1s. Let: v = 1m (m ≥ 0), x = 1n (n ≥ 0)

thus: |v| + |x| ≥ 1. Step 4: Pump the string Now, consider uv 2 wx2 y: uv 2 wx2 y = 1q+m+n This new string must also be in L2 . The length of this string is q + m + n. Step 5: Analyze the result

If m + n = 0, then |vx| = 0, which contradicts our earlier assumption that |vx| ≥ 1.
If m + n > 0, then q + m + n is not prime. This is because q is prime and adding a positive integer (either m or n) results in a composite number. Thus, q + m + n cannot be prime since we would have created a non-prime length.

3.16

Q6: Candidate Exam Question

Explain why Turing machines can recognize more languages than Pushdown Automata, and how this relates to the concept of decidability. Solution:

A Pushdown Automaton can only recognize context-free languages, as it relies on a single stack for memory. This limits its ability to handle languages with increased complexity. By contrast, a Turing Machine can recognize more languages due to its usage of an unlimited read/write tape as memory. It can move in both directions, allowing it to recognize languages that require more than a single stack for memory (i.e. languages that are not context-free).
Turing machines can also be used to address decidability - deciding whether a problem can be solved algorithmically. A problem is decidable if there exists a Turing machine that halts on every input and correctly determines whether it belongs to a specific language.
It is important to note the halting problem, which questions whether a given Turing machine will halt on a particular input. This problem is undecidable, meaning there does not exist a Turing machine that can decide for all possible inputs.

3.17

Q6: Candidate Exam Question

Let L5 be the language {an bn cn | n ≥ 0} over Σ = {a, b, c} It will be assumed that all the transitions not depicted go to the reject state, which may or may not be drawn.

Draw the state diagram for M1 , a deterministic Turing Machine that recognizes L1.

3.18

Q6: Candidate Exam Question

Question: Find the CFG that generates the language accepted by the pushdown automata M = {Q, Σ, Γ, δ, qstart , F }, where: • Q = {q0 , q1 , q2 , q3 } is the set of valid states, • Σ = {a, b, λ} is the input alphabet, • Γ = {a, λ, $} is the stack alphabet, • qstart = q0 is the start state, • F = {q3 } is the set of accept states, and

a → a, R y → y, R

b → b, R y → y, R b → y, R

a → x, R

start

c → y, L

x → x, R

a → a, L c → c, L y → y, L b → b, L

□ → □, L

y → y, R

□ → □, R

y → y, R

start

λ, λ → $

a, λ → a

b, a → λ

λ, $ → λ

b, a → λ

• δ : Q × Σ × Γ → P(Q × Γ) is defined by the following state diagram: 2. Answer: S −→ aSb | λ

3.19

Q6: Candidate Exam Question

Using the Pumping Lemma, prove that the language L = {w ∈ {a, b}∗ | w has twice as many a’s as b’s} is not context free. Answer Proof: Towards contradiction by assuming that L is a context-free language. The Pumping Lemma says that if L is context-free, then there is a pumping length p, where, if any string s ∈ L and is also |s| ≥ p, then s may be divided into s = uvwxy where:

|vwx| ≤ p
|vx| > 1
uv i wxi y ∈ L, for every i ≥ 0. The string we will use is s = a2p bp ∈ L. This has twice as many a’s as it does b’s. This has a length |s| = 3p which does meet the requirement of the Pumping Lemma. Then divide s = uvwxy so that |vwx| ≤ p and |vx| ≥ 1. At this point, since |vwx| ≤ p, this substring can only contain a’s, which implies that v and x only contain a’s. We will now pump up v and x by setting i = 2.

This will add more a’s but keep the same number of b’s. This gives us the string: uv 2 wx2 y, which has more than twice the number of a’s when compared to b’s. Therefore, this pumped up version is ∈ /L Therefore, we have a contradiction which shows that L cannot be context-free.

3.20

Q6: Candidate Exam Question

Show that the language L = {w ∈ {0, 1}∗ | w has an equal number of 0s and 1s} is not context-free using the pumping lemma. Solution: Proof by contradiction: assume L is context-free with pumping length p. Consider the string s = 0p 1p . The length of s is |s| = 2p > p and s ∈ L, so the pumping lemma applies. According to the pumping lemma, we can split s into five parts, s = uvwxy, such that: • vwx has length at most p, • vx ̸= λ, • For all i ≥ 0, uv i wxi y ∈ L. Since vwx has length at most p, it must contain only 0s or only 1s (or a mix that doesn’t change the equal count). Pumping v and x will result in strings with unequal numbers of 0s and 1s when i ̸= 1, meaning uv i wxi y ∈ / L for i ̸= 1. Therefore, the pumping lemma is violated, proving that L is not context-free.

3.21

Q6: Candidate Exam Question

Construct a PDA that accepts the language L1 defined by the grammar S A

−→ −→

0A1 | A 1A | 0S | λ

start

λ, λ −→ $

q1 λ, λ −→ A

λ, λ −→ S λ, S −→ 1 λ, λ −→ 0 λ,A−→λ λ,S−→A 0,0−→λ 1,1−→λ

λ, λ −→ 1

λ, A −→ A q5

λ, $ −→ λ λ, A −→ A q7

λ, λ −→ 0

3.22

Q6: Candidate Exam Question

Consider the language L over the alphabet Σ = {0, 1} defined as: L = {w | w contains at least two 0’s and exactly one 1} (a) Give a context-free grammar that generates L. (b) Draw a pushdown automaton (PDA) that accepts L. (a) Here is a context-free grammar for L: S → 0A0 | 00A A → 0A | 1 | 01 | 10 This grammar works because: 51

• The first rule ensures we have at least two 0’s by requiring one at the start and one at the end (0A0), or two consecutive 0’s (00A). • The second rule allows us to: – Add more 0’s if needed (0A), – Place the single 1 either by itself (1) or next to a 0 (01 or 10). Examples of strings in L: ”001”, ”010”, ”0010”, ”0100”, ”00100”. (b) A PDA that accepts L can be built as follows:

First, verify we see at least two 0’s by counting them on the stack.
When we see a 1, mark it (we can use a state to remember we’ve seen it).
Reject if we see another 1.
Accept when we reach the end if we’ve seen exactly one 1 and at least two 0’s. Simple Example: For the input ”0010”: • Read first 0: push it on stack. • Read second 0: push it on stack. • Read 1: enter ”seen-one” state. • Read 0: stay in ”seen-one” state. • Reach end: accept because we have ≥ 2 zeros (on stack) and saw exactly one 1. Here is a state diagram to illustrate. This could also be a requirement for the question. 0, push 0

λ, push $

1, pop λ push λ

λ, pop 0

q Accept λ, pop $

1, pop λ push λ 0, push 0

3.23

q Reject

λ, pop 0

Q6: Candidate Exam Question

Let Σ = {0, 1}. Find a regular grammar that generates the language L shown below: L = {w | w ∈ Σ∗ such that w has an even number of 0s} . S X X X

−→ −→ −→ −→

X0X0X 0X0 X1X ϵ

3.24

Q6: Candidate Exam Question

Prove that the language: ADF A = {⟨G⟩| G is a DFA that accepted at least 3 strings} Show that if G is decidable TM. Answer To help = visualize the problem. we assume Σ = {a, b } and input G . We create TM M that decide ADF A . For example, the w input string can be w = {a, b, ab}. w is an input that contains 3 strings. Now we turning machine M as follows: M = ” On input w where G is a DFA

Simulate G input string w
if all G input w simulate reach to accepted states, accept
if there are less than 3 strings in w inputs reach accepted states, reject” TM M is a decider based on the proposed turning machine because w input will halt at certain w steps. If there are greater than equal to 3 then M will accept. M will reject if there are at least three inputs or did not reach a non-accepting state. As a result, TM M is decider for ADF A .

3.25

Q6: Candidate Exam Question

Draw a state diagram for the deterministic Turing Machine, M, recognizing the language L = w and w ends with the substring 100, where Σ = {0, 1}. Solution M can be represented by the following state diagram: • States: – q0 (Start state, loops ’0’ until ’1’ occurs) – q1 (State with first occurrence of ’1’) – q2 (State with next occurrence of ’0’ after ’1’, returns to start state if ’1’ occurs again) – q3 (State with next occurrence of ’0’, returns to start state if ’0’ occurs again and q1 if ’1’ occurs again) – qaccepting (Accepting state, string ends with ’100’) • Transitions: – From q0 : ∗ On ’0 → R’, stay in q0 ∗ On ’1 → R’, go to q1 – From q1 : ∗ On ’0 → R’, go to q2 ∗ On ’1 → R’, stay in q1 – From q2 : ∗ On ’0 → R’, go to q3 ∗ On ’1 → R’, go to q0 – From q3 : ∗ On ’0 → R’, go to q0 ∗ On ’1 → R’, go to q1 53

∗ On ’ → L’, go to qaccepting • Start State: q0 • Accepting State: qaccepting • Q: q0 , q1 , q2 ,q3 , qaccepting • Σ: 0, 1 • Γ: 0, 1,

3.26

Q6: Candidate Exam Question

Q: Find a context free grammar for the following language, then create a PDA from the grammar. L = {0n 1m : n, m ≥ 0} Solution: The context-free grammar is: S → 0S | P P → 1P | λ A PDA implementation is:

3.27

Q6: Candidate Exam Question

Let L be the language {w ∈ {0, 1}∗ | w is a palindrome} over Σ = {0, 1}. (i) Draw the state diagram for M , a deterministic Turing Machine that recognizes L. It will be assumed that all the transitions not depicted go to the reject state, which may or may not be drawn. (ii) Is your machine from the previous step a decider? Solution (i)

0/0, R or 1/1, R ∆/∆, R ∆/∆, L

ha 0/∆, L

0/∆, R start

∆/∆, R

q4 ∆/∆, R

0/0, L or 1/1, L

1/∆, R ∆/∆, L

1/∆, L

0/0, R or 1/1, R (ii) As we can see from the previous part, our state diagram of our Turing Machine over the language L correctly decides on the language L. For all palindromes, our machine will accept. For all strings outside of the language, and therefore not a palindrome, our machine will reject.

3.28

Q6: Candidate Exam Question

Q: For the regular expression (0 + 1)10(1), show that it is context-free A: You need to show that there is grammar for it to be context free G = (V, Σ, R, S) V = S, A, B Σ = 0, 1 R= S → A10B A → 0A | 1A | λ B → 1B | λ S=S

3.29

Q6: Candidate Exam Question

Refer, from the first homework question, to the language L1 with the following grammar: S → 0S1 | A A → 1A0 | S | λ Assuming that the starting variable is S, provide the set of inputs of which the language consists. Answer: Let’s analyze the possible inputs created by the given grammar: • Case 1: S production rules With the starting variable being S, the only rules applicable would be S → 0S1 and S → A. For OS1, we can repeatedly utilize this, giving us a forming string of: 0n S1n 55

where n ≥ 1. As we finish applying S → OS1, we must ultimately replace S with A and, with A → λ, get: 0n 1n , n ≥ 1 • Case 2: A production rules If we immediately apply S → A, then we can repeatedly utilize A’s first production rule, giving us a forming string of: 1m A0m where m ≥ 1. As we finish applying 1A0, we can decide to apply A → λ to get: 1m 0m , m ≥ 1 • Case 3: Alternating between S and A rules At first glance, it may seem that L1 would recognize {0n 1n | n ≥ 1} ∪ {1m 0m | m ≥ 1}, but observe the production rule A → S. This indicates that the alternating of 0s and 1s is also allowed. Look at the following valid products: S → A → 1A0 → 1S0 → 10S10 → 10A10 → 101A010 → 101010

(7)

S → 0S1 → 0A1 → 01A01 → 011A001 → 011001

(8)

S → 0S1 → 00S11 → 00A11 → 001A011 → 0011A0011 → 0011S0011 → 00110S10011 → 001100S110011 → 001100A110011 → 001100110011

(9)

The sets we initially thought do not satisfy these strings, even though they’re valid. On the other hand, a common deduction between all of these examples revolves around their ordering. Though different, we observe that, from right to left, the string is equivalent to its complement. Even with the first two cases, if we combine the relevant steps, we will find the following string: 0n 1m 0m 1n | n, m ≥ 1 Though reordered, we see that its complement is visible, and seeing the string reversed we find it equal: – Complement (replace all 0s with 1s and all 1s with 0s: 1n 0m 1m 0n – Reversed (read from right to left): 1n 0m 1m 0n By the behavior of the production rules (with S’s rule being wrapped the opposite way of A’s rule), and the implication that there is an equal amount of 0s and 1s, we find such a unique set of inputs. With this, it is safe to say that: L1 = {w ∈ {0, 1}∗ | its complement, wR = w reversed }

Quartz 4

Explorer

Proposed questions

Proposed questions

Extracted Content (for search)

Solution: n+1 −1 First, verify that 1 + r + r2 + … + rn = r(r−1) is true for n = 1 r2 − 1 (r + 1)(r − 1) r1+1 − 1

Graph View

Table of Contents