19/06/2025, 22:10 Google Gemini

1. Theory of Computation

Example 1.1: DFA Construction

Problem: Construct a DFA that accepts the language of all strings over Σ = {0, 1} that contain an
even number of 0s.

Solution:

We need to keep track of the parity of 0s encountered.

States (Q):
q0 : Represents having seen an even number of 0s (initial state).
​

q1 : Represents having seen an odd number of 0s.

​

Alphabet (Σ): {0, 1}

Start State (q0 ): q0 (since 0 zeros is an even number).
​ ​

Final States (F): F = {q0 } (strings with an even number of 0s are accepted).
​

Transition Function (δ ):
δ(q0 , 0) = q1 (If we are in an even-0s state and see a '0', we move to an odd-0s state).
​ ​

δ(q0 , 1) = q0 (If we are in an even-0s state and see a '1', the parity of 0s doesn't change,
​ ​

so we stay in the even-0s state).

δ(q1 , 0) = q0 (If we are in an odd-0s state and see a '0', we move to an even-0s state).
​ ​

δ(q1 , 1) = q1 (If we are in an odd-0s state and see a '1', the parity of 0s doesn't change,
​ ​

so we stay in the odd-0s state).

DFA Diagram:

+-----+
| | 1
+--| q0 |<--+ (Start and Accept State)
| +-----+ |
| | |
| 0 | | 0
+----->+-----+<--+
| q1 |
+-----+
| 1
+--+

Trace for "1010":

1. Start at q0 . ​

2. Input '1': δ(q0 , 1) ​

= q0 . ​

3. Input '0': δ(q0 , 0) ​ = q1 . ​

[Link] 1/9
19/06/2025, 22:10 Google Gemini

4. Input '1': δ(q1 , 1) ​ = q1 .​

5. Input '0': δ(q1 , 0) = q0 . End at q0 , which is an accept state. So, "1010" is accepted (it has two
​ ​ ​

0s, an even number).

Trace for "001":

1. Start at q0 . ​

2. Input '0': δ(q0 , 0) ​

= q1 .​

3. Input '0': δ(q1 , 0) ​ = q0 .​

4. Input '1': δ(q0 , 1) = q0 . End at q0 , which is an accept state. So, "001" is accepted (it has two
​ ​ ​

0s, an even number).

Trace for "010":

1. Start at q0 . ​

2. Input '0': δ(q0 , 0) ​

= q1 .​

3. Input '1': δ(q1 , 1) ​ = q1 .​

4. Input '0': δ(q1 , 0) = q0 . End at q0 , which is an accept state. So, "010" is accepted (it has two
​ ​ ​

0s, an even number).

Example 1.2: Pumping Lemma Proof

Problem: Prove that the language L = {an bn ∣ n ≥ 0} is not regular using the Pumping Lemma.
Solution:

Proof by Contradiction:
1. Assume L is Regular: Assume, for the sake of contradiction, that L is a regular language.
2. Apply Pumping Lemma: By the Pumping Lemma for regular languages, there exists a
pumping length p ≥ 1 such that any string s ∈ L with ∣s∣ ≥ p can be divided into three parts
s = xyz satisfying the following conditions:
i) ∣y∣ > 0 (The middle part y is non-empty).
ii) ∣xy∣ ≤ p (The combined length of x and y is at most p).
iii) For all i ≥ 0, the string xy i z is also in L.
3. Choose a String: Let's choose a string s ∈ L that is long enough, specifically s = ap bp .
This string s has length ∣s∣ = 2p, which is clearly ≥ p.
Since s ∈ L, it consists of p 'a's followed by p 'b's.
4. Analyze the Division s = xyz :
According to condition (ii), ∣xy∣ ≤ p. Since the string s starts with p 'a's, the substring xy
must consist entirely of 'a's.
This implies that x consists only of 'a's, and y consists only of 'a's. So, y = ak for some
integer k .
According to condition (i), ∣y∣ > 0, so k > 0.
[Link] 2/9
19/06/2025, 22:10 Google Gemini

Since y contains only 'a's, z must contain the remaining 'a's and all the 'b's. So, s =
xak z = ap bp .
5. Pump the String (i = 2):
Now, consider the string s′ = xy 2 z .
s′ = x(ak )(ak )z = xa2k z .
Since s = xak z = ap bp , and y = ak , when we replace y with y 2 , we are effectively adding
another k 'a's to the string.

The new string s′ will have p + k 'a's and p 'b's. (i.e., s′ = ap+k bp ).
Because k > 0, we have p + k = p.
6. Contradiction:
The language L = {an bn ∣ n ≥ 0} requires the number of 'a's to be equal to the number
of 'b's.
However, our pumped string s′ = ap+k bp has p + k 'a's and p 'b's. Since k > 0, p + k = p.
Therefore, s′ ∈/ L.
This contradicts condition (iii) of the Pumping Lemma, which states that xy i z must be in L
for all i ≥ 0.
7. Conclusion: Our initial assumption that L is regular must be false. Therefore, L = {an bn ∣
n ≥ 0} is not a regular language.

Example 1.3: Turing Machine Design

Problem: Design a Turing Machine that accepts the language L = {0n 1n ∣ n ≥ 1} over Σ =
{0, 1}.
(This means strings like "01", "0011", "000111" are accepted).

Solution:

Tape Alphabet (Γ): {0, 1, X, Y , ⊔} (where X, Y are marking symbols, ⊔ is blank).

States (Q): q0 , q1 , q2 , q3 , qaccept , qreject (implicitly, any configuration not leading to qaccept or qreject
​ ​ ​ ​ ​ ​ ​ ​

is a reject state due to non-halting).

Start State (q0 ): ​

Logic:
The TM will work by matching a '0' with a '1'.
1. Scan for the leftmost '0'. Mark it as 'X'.
2. Scan right for the leftmost '1'. Mark it as 'Y'.
3. If a match is found, go back to the beginning to repeat.
4. If all '0's are matched with '1's, verify no extra '1's or '0's.

Transition Function (δ ):
A transition is of the form: (CurrentState, ReadSymbol) →
(N extState, W riteSymbol, M oveDirection)
q0 (Initial state, look for leftmost '0'):
​

[Link] 3/9
19/06/2025, 22:10 Google Gemini

δ(q0 , 0) → (q1 , X, R) : Found a '0', mark it 'X', move right to find a '1'.
​ ​

δ(q0 , Y ) → (q3 , Y , R) : All '0's processed, now scan past 'Y's to check for remaining '1's
​ ​

(should be none).
δ(q0 , ⊔) → (qreject , ⊔, R) : Empty string or string starting with '1' (n=0 not accepted by
​ ​

problem, must be n >= 1). (Alternatively, we could set qaccept for empty string if n ≥ 0 was
​

allowed.)
δ(q0 , 1) → (qreject , 1, R) : String starts with '1' but no '0's.
​ ​

q1 (Scan right to find '1' to match the '0'):

​

δ(q1 , 0) → (q1 , 0, R) : Skip '0's.

​ ​

δ(q1 , Y ) → (q1 , Y , R) : Skip 'Y's (already matched '1's).

​ ​

δ(q1 , 1) → (q2 , Y , L) : Found a '1', mark it 'Y', move left to find the next '0'.
​ ​

δ(q1 , ⊔) → (qreject , ⊔, L) : Ran out of 1s to match the 0s.

​ ​

q2 (Scan left to find the next 'X' or beginning):

​

δ(q2 , X) → (q0 , X, R) : Found the marked '0', move right to q0 to find the next available
​ ​ ​

'0'.
δ(q2 , 0) → (q2 , 0, L) : Skip '0's.
​ ​

δ(q2 , Y ) → (q2 , Y , L) : Skip 'Y's.

​ ​

δ(q2 , ⊔) → (q2 , ⊔, L) : Reached the beginning of the tape. (Could also just transition to
​ ​

q0 from X ).
​

q3 (All '0's matched, check if all '1's are also matched):

​

δ(q3 , Y ) → (q3 , Y , R) : Skip 'Y's (matched '1's).

​ ​

δ(q3 , ⊔) → (qaccept , ⊔, R) : All '0's matched with '1's, and no extra '1's remaining. Accept.
​ ​

δ(q3 , 1) → (qreject , 1, R) : Extra '1's remaining (e.g., "011"). Reject.

​ ​

Trace for "0011":

1. (q0 , 0011⊔)
​ ​

2. δ(q0 , 0) → (q1 , X, R)
​ ​

3. (q1 , X 011⊔)
​ ​

4. δ(q1 , 0) → (q1 , 0, R)
​ ​

5. (q1 , X011⊔)
​ ​

6. δ(q1 , 1) → (q2 , Y , L)
​ ​

7. (q2 , X 0Y 1⊔)
​ ​

8. δ(q2 , 0) → (q2 , 0, L)
​ ​

9. (q2 , X 0Y 1⊔)
​ ​

10. δ(q2 , X) → (q0 , X, R)

​ ​

11. (q0 , X 0Y 1⊔) (Loop back to q0 to find the next '0')

​ ​ ​

[Link] 4/9
19/06/2025, 22:10 Google Gemini

12. δ(q0 , 0) → (q1 , X, R)

​ ​

13. (q1 , XX Y 1⊔)

​ ​

14. δ(q1 , Y ) → (q1 , Y , R)

​ ​

15. (q1 , XXY 1⊔)

​ ​

16. δ(q1 , 1) → (q2 , Y , L)

​ ​

17. (q2 , XX Y Y ⊔)
​ ​

18. δ(q2 , Y ) → (q2 , Y , L)

​ ​

19. (q2 , X X YY ⊔)
​ ​

20. δ(q2 , X) → (q0 , X, R)

​ ​

21. (q0 , XX Y Y ⊔) (All 0s are marked 'X')

​ ​

22. δ(q0 , Y ) → (q3 , Y , R) (Transition to state q3 to check for extra 1s)

​ ​ ​

23. (q3 , XXY Y ⊔)

​ ​

24. δ(q3 , Y ) → (q3 , Y , R)

​ ​

25. (q3 , XXYY ⊔)

​ ​

26. δ(q3 , ⊔) → (qaccept , ⊔, R) ACCEPT

​ ​

2. Compiler Design

Example 2.1: Lexical Analysis using Regular Expressions

Problem: Define regular expressions for the following tokens in a simplified programming language
and show how a lexer would tokenize the input if (count <= 100) { .

Tokens:
KEYWORD (e.g., if , else , while , int )

IDENTIFIER (starts with letter or underscore, followed by letters, digits, or underscores)

INTEGER_LITERAL (sequence of digits)

RELOP (relational operators: <= , >= , == , != , < , > )

LPAREN ( ( )
RPAREN ( ) )

LBRACE ( { )

RBRACE ( } )

Solution:

Regular Expressions:
KEYWORD : if | else | while | int

IDENTIFIER : [a-zA-Z_][a-zA-Z0-9_]*
INTEGER_LITERAL : [0-9]+
[Link] 5/9
19/06/2025, 22:10 Google Gemini

RELOP : <= | >= | == | != | < | >

LPAREN : \( (Backslash escapes the parenthesis as it's a special character in regex)

RPAREN : \)
LBRACE : \{

RBRACE : \}

WHITESPACE : [ \t\n\r]+ (to be ignored by the lexer)

Tokenization of if (count <= 100) { :

The lexer scans the input character by character, attempting to match the longest possible prefix of
the input with one of the defined regular expressions.
1. Input: if (count <= 100) {
The lexer reads i . It could be part of an IDENTIFIER or if .
It reads f . Now it's if . This matches the KEYWORD pattern.
Since if is a full keyword, it's recognized.
Token: ( KEYWORD , "if")
Remaining Input: (count <= 100) {
2. Input: (count <= 100) {
The lexer reads a space. This matches WHITESPACE . It's typically ignored.
Remaining Input: (count <= 100) {
3. Input: (count <= 100) {
The lexer reads ( . This matches LPAREN .
Token: ( LPAREN , "(")
Remaining Input: count <= 100) {
4. Input: count <= 100) {
The lexer reads c . Could be IDENTIFIER .
Reads o , u , n , t . count matches IDENTIFIER .
Token: ( IDENTIFIER , "count")
Remaining Input: <= 100) {
5. Input: <= 100) {
Reads a space (whitespace, ignored).
Reads <= . This matches RELOP . It's the longest match for < followed by = .
Token: ( RELOP , "<=")
Remaining Input: 100) {
6. Input: 100) {
Reads a space (whitespace, ignored).
Reads 1 . Could be INTEGER_LITERAL .
Reads 0 . 10 .
Reads 0 . 100 . This matches INTEGER_LITERAL .

[Link] 6/9
19/06/2025, 22:10 Google Gemini

Token: ( INTEGER_LITERAL , "100")

Remaining Input: ) {
7. Input: ) {
Reads ) . This matches RPAREN .
Token: ( RPAREN , ")")
Remaining Input: {
8. Input: {
Reads a space (whitespace, ignored).
Reads { . This matches LBRACE .
Token: ( LBRACE , "{")
Remaining Input: `` (End of input)

Final Token Stream:

( KEYWORD , "if")
( LPAREN , "(")
( IDENTIFIER , "count")
( RELOP , "<=")
( INTEGER_LITERAL , "100")
( RPAREN , ")")
( LBRACE , "{")

Example 2.2: Parsing with a CFG (Parse Tree)

Problem: Given the following Context-Free Grammar for simple arithmetic expressions:

E →E+T ∣ T
T → T ∗F ∣ F
F → (E) ∣ id
Draw the parse tree for the input string id + id * id .

Solution:

We perform a leftmost derivation and construct the parse tree simultaneously.

Derivation Steps:
1. E (Start symbol)
2. ⇒ E + T (Using production E → E + T )
3. ⇒ T + T (Using production E → T )
4. ⇒ id + T (Using production T → F , then F → id)
5. ⇒ id + T ∗ F (Using production T → T ∗ F )
6. ⇒ id + id ∗ F (Using production T → F , then F → id)
7. ⇒ id + id ∗ id (Using production F → id)
[Link] 7/9
19/06/2025, 22:10 Google Gemini

Parse Tree:

E
/|\
E + T
/ /|\
T T * F
| | |
F F id
| |
id id

Explanation:
The parse tree visually represents the derivation.
The root is the start symbol E .
Each internal node is a non-terminal, and its children correspond to a production rule applied
to that non-terminal. For example, E expands to E + T .
The leaves of the tree, read from left to right, form the input string id + id * id .

This parse tree correctly shows the precedence of multiplication over addition, as id * id forms a
T first, before being combined with the + id .

Example 2.3: Intermediate Code Generation (Three-Address Code)

Problem: Generate three-address code (TAC) for the following C-like statement:

result = (a + b) * (c - d) / 2;

Solution:

Three-address code statements typically have the form x = y op z , where op is an operator,

and x, y, z are operands. Temporaries (e.g., t1, t2 ) are introduced for intermediate results.

1. a + b : This is the first sub-expression.

t1 = a + b

2. c - d : This is the second sub-expression.

t2 = c - d
3. (a + b) * (c - d) : Now multiply the results of the previous two operations.
t3 = t1 * t2
4. ... / 2 : Finally, divide the result by 2.
t4 = t3 / 2
5. result = ... : Assign the final result to the result variable.
result = t4

Complete Three-Address Code:

[Link] 8/9
19/06/2025, 22:10 Google Gemini

t1 = a + b
t2 = c - d
t3 = t1 * t2
t4 = t3 / 2
result = t4

[Link] 9/9