[go: up one dir, main page]
Scribd
Upload
3 views8 pages

D1

The document outlines an assignment due on November 4, 2024, which involves converting a given NFA to a DFA using the subset construction method. It includes two questions that require the creation of transition functions and subset construction tables for the NFA, followed by converting these tables into DFA format. The assignment is structured to guide students through the steps of the conversion process.

Uploaded by

mohammed000junaid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views8 pages

D1

The document outlines an assignment due on November 4, 2024, which involves converting a given NFA to a DFA using the subset construction method. It includes two questions that require the creation of transition functions and subset construction tables for the NFA, followed by converting these tables into DFA format. The assignment is structured to guide students through the steps of the conversion process.

Uploaded by

mohammed000junaid
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

ASSI

GNMENT#02

Submi
ssi
onDeadl
i
ne:
Nov
ember04,
2024

Submi
ssi
on:
[1Mar
k]

Quest
ionNo.1:
Conv
ertt
hef
oll
owi
ngNFAt
oDFAbyusi
ngsubset
const
ruct
ionmet
hod.

(
Hint:
fir
stmaketheNFAt r
ansi
tionfunct
ionthenmakethesubsetconst
ruct
ion
t
ableandthenconver
tthetabl
et oDFA)[1.
0+1. 0=2.
0mark]

0,
1

0
0 1

1
Answer

t
ransi
ti
onf
unct
ion
δ 0 1

A C Ø

B Ø {
A,C}

*
C {
A,B} A
subsetconst
ruct
iont
abl
e
δ 0 1

A C Ø

*
C {
A,B} A

AB C {
A,C}

*
AC {
A,B,
C} A

*
ABC {
A,B,
C} {
A,C}
conv
ertt
het
abl
etoDFA

A C
0

1
0
0

1
A, A,
B
C

A,
B,
C

0
Quest
ionNo.2:
Conv
ertt
hef
oll
owi
ngNFAt
oDFAbyusi
ngsubset
constr
ucti
onmet hod.(
Hint:
fir
stmaket
heNFAtransi
ti
onfunct
iont
henmake
thesubsetconst
ructi
ontabl
eandthenconv
ertt
hetabl
etoDFA)[1.
0+1.0=
2.0marks]

Answer

NFAt
ransi
ti
onf
unct
ion
δ a b

0 {
1,2,
3} {
2,3}

*
1 {
1,2} {
2,3}

2 Ø {
3,4}

3 {
4} {
2,3,
4}

4 Ø Ø

maket
hesubsetconst
ruct
iont
abl
e
δ a b

{
0} {
1,2,
3} {
2,3}
*
{1,
2,
3} {
1,2,
4} {
2,3,
4}

*
{1,
2,
4} {
1,2} {
2,3,
4}

*
{1,
2} {
1,2} {
2,3,
4}

{
2,3,
4} {
4} {
2,3,
4}

{
2,3} {
4} {
2,3,
4}

{
4} Ø Ø

conv
ertt
het
abl
etoDFA

a
{
0} 1,
2,
3
}

b
a
b

b
b
b 1,
2,
4}
2,
3} 2,
3,
4}
{
{

a
a b

{
1,2}

{
4}
a

You might also like