# 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:

    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:

    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:

    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:

    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:

    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:

    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:

    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] |

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.

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

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.

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

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.

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.

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

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"]
    
}