---
# System prepended metadata

title: Theory of Computation Unit I Assignment

---

# Theory of Computation Unit I Assignment

### 1. Give DFA’s accepting the following languages over the alphabet {0, 1}* and list down the five tubles with a state diagram. (Note : Use more than 2 states)



#### a. L = \{ω | ω has at least one 1 }
+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 1, 01, 10, 11, ...}
    - no. state = min lenght +1 = 1+1 = 2
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q0: 0
        q0 --> q1: 1
        q1 --> q1: {0,1}
        
    ```
+ Five tuples:
    - Q = \{q0, q1}
    - S = q0
    - F = q1
    - Σ = \{0,1}
    - P = 

|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | q0     | q1     |
| q1     | q1     | q1     |


#### b. L = \{ω | ω is a string of even length}
+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 00, 01, 10, 11, 0000, 0001, ...}
    - no. state = min lenght +1 = 2+1 = 3
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q1: {0,1}
        q1 --> q2: {0,1}
        q2 --> q1: {0,1}
    ```
+ Five tuples:
    - Q = \{q0, q1, q2}
    - S = q0
    - F = q2
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | q1     | q1     |
| q1     | q2     | q2     |
| q2     | q2     | q2     |

#### c. L = \{ω | ω is either begin or end with 01}

+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 01, 001 ,010, 011, 0100, 0101, ...}
    - no. state = min lenght +1 = 2+1 = 3
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q0: 1
        q0 --> q1: 0
        q1 --> q1: 0
        q1 --> q2: 1
        q2 --> q0: 1
        q2 --> q1: 0
    ```
+ Five tuples:
    - Q = \{q0, q1, q2}
    - S = q0
    - F = q0
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | q1     | q0     |
| q1     | q1     | q2     |
| q2     | q1     | q0     |

#### d. L = \{ω | ω is divided by 3 and remainder is 1}

+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 10, 100 ,110...}
    - no. state = min lenght +1 = 2+1 = 3
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> [*]: 0
        q0 --> q1: 1
        q1 --> q2: {0,1}
        q2 --> q2: {0,1}
    ```
+ Five tuples:
    - Q = \{q0, q1, q2}
    - S = q0
    - F = q2
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | DS     | q1     |
| q1     | q2     | q2     |
| q2     | q2     | q2     |

#### e. L = \{ω | ω when interpreted in reverse as a binary integer, is divisible by 5, Example of strings in the language are 0, 10011, 1001100, and 0101}

+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 0, 101, 0101 ,1010, ...}
    - no. state = min lenght +1 = 1+1 = 2
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q0: 1
        q0 --> q1: 0
        q1 --> q0 : 1
        q1 --> q1 :0
    ```
+ Five tuples:
    - Q = \{q0, q1}
    - S = q0
    - F = q1
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | q0     | q1     |
| q1     | q1     | q0     |


f. L = \{ω | ω is beginning with a 1 that, when interpreted as a binary integer is a multiple of 5. For example, strings 101, 1010 and 1111 are in the language; 0, 100 and 111 are not}

+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 101,1010, 1111,...}
    - no. state = min lenght +1 = 3+1 = 2
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q1: 1
        q0 --> [*]: 0
        q1 --> q2: 0
        q1 --> q3:1
        q2 --> q3: 1
        q2 --> q2:0
        q3 --> q3: {0,1}
    ```
+ Five tuples:
    - Q = \{q0, q1, q2, q3}
    - S = q0
    - F = q3
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | DS     | q1     |
| q1     | q2     | q3     |
| q2     | q2     | q3     |
| q3     | q3     | q3     |

g. L = \{ω | ω is start and end with the same symbol}

+ Kleen closure:
    - Σ* =  \{0,1}*
    - Σ* =  \{ε, 00, 11, 101, 000, 111, ...}
    - no. state = min lenght +1 = 2+1 = 3
+ State diagram:
    ```mermaid
    stateDiagram
        q0 --> q1: {0,1}
        q1 --> q2: {0,1}
        q2 --> q2: {0,1}
    ```
+ Five tuples:
    - Q = \{q0, q1, q2, q3}
    - S = q0
    - F = q3
    - Σ = \{0,1}
    - P = 
    
|  | 0 | 1 |
| -------- | -------- | -------- |
| q0     | q1     | q1     |
| q1     | q2     | q2     |
| q2     | q2     | q2     |


### 2. Convert the following NFA to a DFA

#### a. 
- NFA


|          |    0     |     1    |
| -------- | -------- | -------- |
|    p     |  \{p,q}  |  \{p}    |
|    q     |  \{r}  |  \{r}    |
|    r     |  \{s}  |  DS    |
|    s*     |  \{s}  |  \{s}    |

- DFA


|          |    0     |     1    |
| -------- | -------- | -------- |
|    p     |  \[p,q]  |  \[p]    |
|    \[p,q]     |  \[p,q,r]  |  \[p,r]    |
|    \[p,q,r]     |  \[p,q,r,s]  |  \[p,r]    |
|    \[p,r]     |  \[p,q,s]  |  \[p]    |
|    \*\[p,q,r,s]     |  \[p,q,r,s]  |  \[p,r,s]    |
|    \*\[p,r,s]     |  \[p,q,r,s]  |  \[p,r,s]    |
|    \*\[p,r,s]     |  \[p,q,s]  |  \[p,s]    |
|    \*\[p,s]     |  \[p,q,s]  |  \[p,s]    |

```graphviz
digraph finite_state_machine {
    rankdir=LR;
    node [shape = doublecircle] "[p,q,r,s]", "[p,r,s]", "[p,s]";
    node [shape = point] 0;
    node [shape= circle];
    0->p[label="start"]
    p -> "[p,q]" [label="0"]
    p -> "p" [label="1"]
    "[p,q]" -> "[p,q,r]" [label="0"]
    "[p,q]" -> "[p,r]" [label="1"]
    "[p,q,r]" -> "[p,q,r,s]" [label="0"]
    "[p,q,r]" -> "[p,r]" [label="1"]
    "[p,q,r,s]" -> "[p,q,r,s]" [label="0"]
    "[p,q,r,s]" -> "[p,r,s]" [label="1"]
    "[p,r,s]" -> "[p,q,r,s]" [label="0"]
    "[p,r,s]" -> "[p,r,s]" [label="1"]
    "[p,r,s]" -> "[p,q,s]" [label="0"]
    "[p,r,s]" -> "[p,s]" [label="1"]
    "[p,s]" -> "[p,q,s]" [label="0"]
    "[p,r,s]" -> "[p,s]" [label="1"]
    
}
```

#### b.

- NFA

|          |    0     |     1    |
| -------- | -------- | -------- |
|    p     |  \{q,s}  |  \{q}    |
|    q*     |  \{r}  |  \{q,r}    |
|    r     |  \{s}  |  \{p}   |
|    s*     |  DS  |  \{p}    |

- DFA

|          |    0     |     1    |
| -------- | -------- | -------- |
|     p     |  \[q,s]  |  \[q]    |
|    \[q,s]     |  \[r]  |  \[p,q,r]    |
|    \[q]     |  \[r]  |  \[q,r]    |
|    \[r]     |  \[s]  |  \[p]    |
|    \*\[p,q,r]     |  \[q,r,s]  |  \[p,q,r]    |
|    \[q,r]     |  \[r,s]  |  \[p,q,r]    |
|    \*\[s]     |  DS  |  \[p]    |
|    \*\[p,s]     |  \[q,s]  |  \[p,q]    |
|    \*\[r,s]     |  \[s]  |  \[p]    |
|    \*\[p,q]     |  \[q,r,s]  |  \[q,r]    |
|    \*\[q,r,s]     |  \[r,s]  |  \[p,q,r]    |


### 3. Minimize the DFA diagram

#### a.

```graphviz
digraph finite_state_machine {
    rankdir=LR;
    node [shape = doublecircle] 5, 6;
    node [shape= circle]
    1->2[label="a"]
    1->3[label="b"]
    2->1[label="a"]
    2->3[label="b"]
    3->4[label="a"]
    3->5[label="b"]
    4->6[label="b"]
    4->1[label="a"]
    5->4[label="b"]
    5 -> 7[label="a"]
    6->7[label="a"]
    6->4[label="b"]
    7->3[label="a"]
    7->6[label="b"]
}
```


- No dead state
- Q = \{1,2,3,4,5,6,7}
- F = \{5,6}
- Q-F= \{1,2,3,4,7}
- Transition table

|          |    a     |    b     |
| -------- | -------- | -------- |
| 1    |   2   |  3    |
| 2    |   1   |  3    |
| 3    |   4   |  5    |
| 4    |   1   |  6    |
| 5    |   7   |  4    |
| 6    |   7   |  4    |
| 7    |   3   |  6    |

- Calculate 1

{1,2,3,4,7}{5,6}
=> {1,2}{3,4,7}{5,6}

- calculate 2

=> {1,2}{3}{4}{7}{5,6}

- state diagram

```graphviz
digraph finite_state_machine {
	rankdir=LR;
	node [shape = doublecircle] "5,6";
    node [shape = point] o;
	node [shape = circle];
    o -> "1,2" [label="start"]
	"1,2" ->  "1,2"[ label = "a" ];
	"1,2" ->  3[ label = "b" ];
    4 -> "1,2"[label="a"]
    3 -> 4 [label="a"]
    3-> "5,6" [label="b"]
    4 -> "5,6" [label="b"]
    "5,6"->7[label="a"]
    "5,6"->4 [label="b"]
    7->"5,6"[label="b"]
    7->3[label="a"]
}
```
#### b.

```graphviz
digraph f{
    rankdir=LR;
    size="10,15"
    node [shape = doublecircle] q5, q6;
    node [shape = point] 0;
    node [shape= circle];
    0->q0 [label="start"]
    q0->q1 [label="a"]
    q0->q2 [label="b"]
    q1->q2 [label="a"]
    q1->q3 [label="b"]
    q2->q4 [label="a"]
    q2->q6 [label="b"]
    q3->q4 [label="a"]
    q3->q5 [label="b"]
    q4->q3 [label="a"]
    q4->q6 [label="b"]
    q5->q5 [label="a"]
    q5 -> q6 [label="b"]
    q6->q5[label="a"]
    q6->q6 [label="b"]
}
```

- no deadstate
- Q=\{q0,q1,q2,q3,q4,q5,q6}
- F=\{q5,q6}
- Q-F = \{q0,q1,q2,q3,q4}
- Transition table



|  | a | b |
| -------- | -------- | -------- |
| q0| q1     | q2    |
| q1| q1     | q3    |
| q2| q4     | q6    |
| q3| q4     | q5    |
| q4| q3     | q6    |
| q5| q5     | q6    |
| q6| q5     | q6    |

- Calculate 1
    - {q0,q1,q2,q3,q4} {q5,q6}
    => {q0,q1}{q2,q3,q4}{q5,q6}
- Calculate 2
    - {q0}{q1}{q2,q3,q4}{q5,q6}

- State Diagram

```graphviz
digraph f{
    rankdir=LR;
    size="10,15"
    node [shape = doublecircle] "q5,q6";
    node [shape = point] 0;
    node [shape= circle];
    0->q0 [label="start"]
    q0->q1 [label="a"]
    q1 ->"q1,q2,q3" [label="{a,b}"]
    "q1,q2,q3" ->"q1,q2,q3" [label="a"]
    "q1,q2,q3" -> "q5,q6"[label="b"]
}
```

### 4.Convert ε-NFA to DFA

### a. 



```graphviz
digraph f{
    rankdir=LR;
    size="10,15"
    node [shape = doublecircle] 6;
    node [shape = point] 0;
    node [shape= circle];
    0->1 [label="start"]
    1 ->2 [label="ε"]
    1 ->4 [label="ε"]
    2 ->3 [label="b"]
    3 ->3 [label="a"]
    3 ->6 [label="ε"]
    4 ->5 [label="a"]
    5 ->6 [label="a"]
    5 ->4 [label="b"]
    5 ->3 [label="ε"]   
}


```

- Epsilon Closure
    - 1 ={1,2,4}
    - 2={2}
    - 3={3,6}
    - 4={4}
    - 5={5,3,6}
    - 6={6}

- Transition Table 
    - NFA

    | | a| b | epsilon|
    | -------- | -------- | --------|-------- |
    | 1     | DS | DS| {2,4} |
    | 2     | DS   | 3 |DS|
    | 3     | 3   | DS | 6*|
    | 4     | 5   | DS |DS|
    |5|6*|4|3|
    | 6*   | DS  | DS | DS|
    
    - DFA

    

    | | a | b |
    | -------- | -------- | -------- |
    | 2     | DS     | 3     |
    | 3    | 3     | DS     |
    | 4     |   5   | DS    |
    | 5     |   6   | 4    |
    | \{1,2,4}|   5   | 3    |
    | \{3,6}     |   3   | DS    |
    | \{5,3,6}     |   \{6,3}   | 4  |


### a. 

```graphviz
digraph f{
    rankdir=LR;
    size="10,15"
    node [shape = doublecircle] 4;
    node [shape = point] 0;
    node [shape= circle];
    0->1 [label="start"]
    1 ->2 [label="ε"]
    1 ->5 [label="ε"]
    5 ->7 [label="ε"]
    5 ->6 [label="ε"]
    8 ->1 [label="ε"]
    7->8[label="b"]
    6->8[label="a"]
    2->3[label="A"]  
    3->4[label="b"]
}
```

- Epsilon Closure
    - 1 ={1,2,5,6,7}
    - 2={2}
    - 5={5,6,7}
    - 6={6}
    - 7={7}
    - 8={8,1,2,5,6,7}

- Transition Table 
    - NFA

    | | a| b | epsilon|
    | -------- | -------- | --------|-------- |
    | 1     | DS | DS| {2,5} |
    | 2     | 3   | DS |DS|
    | 3     | DS   | 4* | DS|
    |5|DS|Ds|{6,7}|
    | 6   | 8  | DS | DS|
    |7|DS|8|Ds|
    
    - DFA

    | | a | b |
    | -------- | -------- | -------- |
    | 2     | 3   |  DS    |
    | 3    | DS     | 4     |
    | 6    |   8   | Ds    |
    | 7    |   Ds   | 8    |
    | \{1,2,5,6,7}|   \{3,8} | 8 |
    | \{3,8}    |   DS   | 4  |
    | \{5,6,7}     |   8   | 8 |
    | \{8,1,2,3,5,6,7}    |   \{3,8}   | \{4,8}|
    


- State diagram

```graphviz
digraph f{
    rankdir=LR;
    size="10,15"
    node [shape = doublecircle] 4;
    node [shape = point] 0;
    node [shape= circle];
    0->2 [label="start"]
    2->3 [label="a"]
    3 ->4 [label="b"]
    6->8[label="a"]
    7->8[label="b"]
    "1,2,3,4,5,6,7"->"3,8"[label="a"]
    "1,2,3,4,5,6,7"->8[label="b"]
    "3,8"->4[label="b"]
    "5,6,7"->8[label="{a,b}"]
    "8,1,2,3,5,6,7"->"3,8"[label="a"]
    "8,1,2,3,5,6,7"->"4,8"[label="b"]
    
}
```