Assignment Three

1. Question One

1.1. a

1a.excalidraw.png

1.2. b

1b.excalidraw.png

1.3. c

1c.excalidraw.png

1.4. d

1d.excalidraw.png

1.5. e

1e.excalidraw.png

1.6. f

1f.excalidraw.png

2. Question Two

State	a	b	e
0	φ	φ	{1, 3}
1	{2, 4}	{4}	φ
2	{2}	φ	φ
3	φ	{4}	φ
4	φ	{4}	φ

3. Question Three

State	a	b
0	1	0
1	1	2
2	1	3
3	1	0

4. Question Four

4.1. a

4a.excalidraw.png

4.2. b

DFA State	NFA States	a	b	c
d₀	{s₀, s₁, s₂, s₅, s₉}	{s₃, s₆} (d₁)	s_e	s_e
d₁	{s₃, s₆}	s_e	{s₄, s₈, s₉, s₁, s₂, s₅} (d₂)	{s₇, s₈, s₉, s₁, s₂, s₅} (d₃)
d₂	{s₄, s₈, s₉, s₁, s₂, s₅}	{s₃, s₆} (d₁)	s_e	s_e
d₃	{s₇, s₈, s₉, s₁, s₂, s₅}	{s₃, s₆} (d₁)	s_e	s_e

4b.excalidraw.png

4.3. c

partition	a	b	c
{d₁}, {d₀, d₂, d₃}	{d₀, d₂, d₃} ⇒ {d₁, d₀, d₀}	{d₀, d₂, d₃} ⇒ {-, -, -}	{d₀, d₂, d₃} ⇒ {-, -, -}
{d₁}, {d₀}, {d₂, d₃}	{d₂, d₃} ⇒ {d₀, d₀}	{d₂, d₃} ⇒ {-, -}	{d₂, d₃} ⇒ {-, -}

4c.excalidraw.png

5. Question Five

5.1. regex 1

5.1.1. NFA

51a.excalidraw.png

5.1.2. DFA

DFA State	NFA States	1	0
d₀	{s₀, s₁, s₂, s₄, s₇}	{s₁, s₂, s₃, s₄, s₆, s₇} (d₁)	{s₁, s₂, s₄, s₅, s₆, s₇} (d₂)
d₁	{s₁, s₂, s₃, s₄, s₆, s₇}	d₁	d₂
d₂	{s₁, s₂, s₄, s₅, s₆, s₇}	d₁	d₂

51b.excalidraw.png

5.1.3. Minimization

partition	1	0
{d₀, d₁, d₂}	{d₀, d₁, d₂} ⇒ {d₁, d₁, d₁}	{d₀, d₁, d₂} ⇒ {d₂, d₂, d₂}

51c.excalidraw.png

5.2. regex 2

5.2.1. NFA

52a.excalidraw.png

5.2.2. DFA

DFA State	NFA States	1	0
d₀	{s₀, s₁, s₂, s₃, s₅, s₁₁, s₆, s₁₂ }	{s₁, s₂, s₃, s₅, s₆, s₇, s₈, s₁₀, s₁₁, s₁₂} (d₁)	{s₁, s₂, s₃, s₄, s₅, s₁₁, s₆, s₁₂} (d₂)
d₁	{s₁, s₂, s₃, s₅, s₆, s₇, s₈, s₁₀, s₁₁, s₁₂}	d₁	{s₁, s₂, s₃, s₄, s₅, s₉, s₁₁, s₆, s₁₂} (d₃)
d₂	{s₁, s₂, s₃, s₄, s₅, s₁₁, s₆}	d₁	d₂
d₃	{s₁, s₂, s₃, s₄, s₅, s₉, s₁₁, s₆, s₁₂}	d₁	d₂

52b.excalidraw.png

5.2.3. Minimization

partition	1	0
{d₀, d₁, d₂, d₃}	{d₀, d₁, d₂, d₃} ⇒ {d₁, d₁, d₁, d₁}	{d₀, d₁, d₂, d₃} ⇒ {d₂, d₃, d₂, d₂}

52c.excalidraw.png

6. Question Six

6.1. a

6.1.1. DFA

6a.excalidraw.png

6.1.2. catMap

{
  '-': 'sign',
  '+': 'sign',
  [0-9]: 'digit',
  'e': 'scntfc'
}

6.1.3. transMap

{
  's0': {
    'sign': 's1',
    'digit': 's2',
  },
  's1': {
    'digit': 's2',
  },
  's2': {
    'digit': 's2',
    'scntfc': 's3',
  },
  's3': {
    'sign': 's4',
    'digit': 's5',
  },
  's4': {
    'digit': 's6',
  },
  's5': {
    'digit': 's6',
  },
  's6': {
    'digit': 's6',
  },
}

6.1.4. tokenTypes

{
  's2': 'integer',
  's6': 'integer,
}

6.2. b

6.2.1. DFA

6b.excalidraw.png

6.2.2. catMap

{
  [a-zA-Z]: 'letter',
  '_': 'letter',
  [0-9]: 'digit',
}

6.2.3. transMap

{
  's1': {
    'letter': 's2'
  },
  's2': {
    'letter': 's2',
    'digit': 's2',
  },
}

6.3. c

6.3.1. DFA

6c.excalidraw.png

6.3.2. catMap

{
  [^(\n)*/]: 'nonc',
  '\n': 'newline',
  'eof': 'eof',
  '/': 'slash',
  '*': 'star'
}

6.3.3. transMap

{
  's0': {
    'slash': 's1',
  },
  's1': {
    'slash': 's2',
    'star': 's4',
  },
  's2': {
    'nonc': 's2',
    'newline': 's3',
    'eof': 's3'
  },
  's4': {
    'nonc': 's4',
    'star': 's5',
  },
  's5': {
    'nonc': 's4',
    'newline': 's4',
    'slash': 's6'
  }
}

6.3.4. tokenType

{
  's3': 'singleLineComment',
  's6': 'multiLineComment',
}