DFAs and NFAs Questions

you have to study the slides and there is a small quiz 14 questions in 40 min. Probably true or false questions about DFAs and NFAs.

HW 04-01—-SOLUTION—- Finite Automata DFAs without JFLAP
EXAMPLE
Problems 1 – 4 all ask you to answer several things about a DFA. So that you understand what I’m asking, I’m going to do
an example first. My example answers will be in bold fuchsia.
●
Answer all of the following questions for the DFA shown in Figure 0 above. In each case, specify the sequence of
states that you visit and then answer yes or no
■ Does it accept the string Λ 1, no
■ Does it accept the string a 1, 2 yes
■ Does it accept the string aa 1, 2,3, no
■ Does it accept the string aaa 1, 2,3,4 no
■ Does it accept the string aaaa 1, 2,3,4,2 yes
■ Does it accept the string aaaaa 1, 2,3,4,2 ,3 no
1, 2,3,4,2,3, 4 no
■ Does it accept the string aaaaaa
●
●
Is the language of this DFA finite or infinite?
Infinite
Give a set that represents what this DFA accepts: {a3n+1| n ∈ℕ}
●
Give a regular expression that represents what this DFA accepts: a(aaa)*
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 1
a. Answer all of the following questions for the DFA shown in Figure 1 above
In each case, specify the sequence of states that you visit and then answer yes or no
i.
Does it accept the string Λ State 1, Yes
ii.
Does it accept the string a State 1 -> State 2, No
iii.
Does it accept the string b State 1 -> State 4, No
iv.
Does it accept the string ab State 1 -> State 2 -> State 2, No
v.
Does it accept the string ba State 1 -> State 4 -> State 3, Yes
vi.
Does it accept the string aa State 1 -> State 2 -> State 2, No
vii.
Does it accept the string bb State 1 -> State 4 -> State 2, No
viii.
Does it accept the string aaa State 1 -> State 2 -> State 2 -> State 2, No
ix.
Does it accept the string aab State 1 -> State 2 -> State 2 -> State 2, No
x.
Does it accept the string aba State 1 -> State 2 -> State 2 -> State 2, No
xi.
Does it accept the string abb State 1 -> State 2 -> State 2 -> State 2, No
xii.
Does it accept the string baa State 1 -> State 4 -> State 3 -> State 2, No
xiii.
Does it accept the string bab State 1 -> State 4 -> State 3 -> State 3, No
xiv.
Does it accept the string bba State 1 -> State 4 -> State 2 -> State 2, No
xv.
Does it accept the string bbb State 1 -> State 4 -> State 2 -> State 2, No
b. Is the language of this DFA finite or infinite??
Infinite
c. [optional] Give a set that represents what this DFA accepts
{babn | n ∈ ℕ} U {Λ}
d. Give a regular expression that represents what this DFA accepts
bab*+Λ
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 2
e. Answer all of the following questions for the DFA shown in Figure 2 above
In each case, specify the sequence of states that you visit and then answer yes or no
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
x.
xi.
xii.
xiii.
xiv.
xv.
f.
Does it accept the string Λ State 1, no
Does it accept the string a State 1 -> State 2, Yes
Does it accept the string b State 1 -> State 4, Tes
Does it accept the string ab State 1 -> State 2 -> State 5, No
Does it accept the string ba State 1 -> State 4 -> State 4, Yes
Does it accept the string aa State 1 -> State 2 -> State 3, Yes
Does it accept the string bb State 1 -> State 4 -> State 5, No
Does it accept the string aaa State 1 -> State 2 -> State 3 -> State 5, No
Does it accept the string aab State 1 -> State 2 -> State 3 -> State 5, No
Does it accept the string aba State 1 -> State 2 -> State 5 -> State 5, No
Does it accept the string abb State 1 -> State 2 -> State 5 -> State 5, No
Does it accept the string baa State 1 -> State 4 -> State 4 -> State 4, Yes
Does it accept the string bab State 1 -> State 4 -> State 4 -> State 5, No
Does it accept the string bba State 1 -> State 4 -> State 5 -> State 5, No
Does it accept the string bbb State 1 -> State 4 -> State 5 -> State 5, No
Is the language of this DFA finite or infinite??
Infinite
g. [optional] Give a set that represents what this DFA accepts
{ban | n ∈ ℕ} U {a, aa}
h. Give a regular expression that represent what this DFA accepts
ba*+a+aa
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 3
Answer all of the following questions for the DFA shown in Figure 3 above (yes, it’s different from Figure 2 – look at state
4)
[i through xv are optional!!,
In each case, specify the sequence of states that you visit and then answer yes or no
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
x.
xi.
xii.
xiii.
xiv.
xv.
Does it accept the string Λ State 1, no
Does it accept the string a State 1 -> State 2, Yes
Does it accept the string b State 1 -> State 4, Yes
Does it accept the string ab State 1 -> State 2 -> State 5, No
Does it accept the string ba State 1 -> State 4 -> State 5, No
Does it accept the string aa State 1 -> State 2 -> State 3, Yes
Does it accept the string bb State 1 -> State 4 -> State 5, No
Does it accept the string aaa State 1 -> State 2 -> State 3 -> State 5, No
Does it accept the string aab State 1 -> State 2 -> State 3 -> State 5, No
Does it accept the string aba State 1 -> State 2 -> State 5 -> State 5, No
Does it accept the string abb State 1 -> State 2 -> State 6 -> State 5, No
Does it accept the string baa State 1 -> State 4 -> State 5 -> State 5, No
Does it accept the string bab State 1 -> State 4 -> State 5 -> State 5, No
Does it accept the string bba State 1 -> State 4 -> State 5 -> State 5, No
Does it accept the string bbb State 1 -> State 4 -> State 5 -> State 5, No
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
b. Is the language of this DFA finite or infinite??
Finite
c. Give a set that represents what this DFA accepts
{a, b, aa}
d. [optional] Give a regular expression that represent what this DFA accepts
a+b+aa
Problem 4
[i through xv are optional!!,
e. Answer all of the following questions for the DFA shown in Figure 4 above
In each case, specify the sequence of states that you visit and then answer yes or no
[i through xv are optional!!, the other parts are required]
i.
Does it accept the string Λ State q0, no
ii.
Does it accept the string 0 State q0 → q1, no
iii.
Does it accept the string 1 State q0 → q3, yes
iv.
Does it accept the string 00 State q0 → q1 → q2, no
v.
Does it accept the string 01 State q0 → q1 → q3, yes
vi.
Does it accept the string 10 State q0 → q3 → q3, yes
vii.
Does it accept the string 11 State q0 → q3 → q3, yes
viii.
Does it accept the string 000 State q0 → q1 → q2 → q0, no
ix.
Does it accept the string 001 State q0 → q1 → q2 → q3, yes
x.
Does it accept the string 010 State q0 → q1 → q3 → q3, yes
xi.
Does it accept the string 011 State q0 → q1 → q3 → q3, yes
xii.
Does it accept the string 100 State q0 → q3 → q3 → q3, yes
xiii.
Does it accept the string 101 State q0 → q3 → q3 → q3, yes
xiv.
Does it accept the string 110 State q0 → q3 → q3 → q3, yes
xv.
Does it accept the string 111 State q0 → q3 → q3 → q3, yes
f.
Is the language of this DFA finite or infinite??
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Infinite
g. Give a regular expression that represents what this DFA accepts
0*1(0+1)*
Problem 5
a. What is the set accepted by the DFA in figure 5?
Correct answers for the set accepted by fig 5 (there are many more
options- if you have a question, ask me!):
1. {a, aa, aaa, …}
2. {a}+ (note that’s a plus not a star)
3. {an+1 | n ∈ℕ} (note that exponent has to be n+1 not n)
4. {an | n ∈ℕ and n>=1}
b. Give a regular expression that represents that language
Correct answers for the regular expression:
aa*
a*a
(There are, of course, other options, but I don’t really see people
coming up with them – again, ask me if you have a question. Note
that a* is incorrect and a+ is also incorrect because there is no + in
regular expression land!)
Problem 6
a. What is the set accepted by the DFA in figure 6?
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
{an | n ∈ N}
b. Give a regular expression that represents that language
a*
Problem 7
a. What is the set accepted by the DFA in figure 7?
{Λ}
b. Give a regular expression that represents that language
Λ
Problem 8
a. [optional]What is the set accepted by the DFA in figure 8 (Yes, this is a DFA!!) ?
{} or ∅
b. Give a regular expression that represents that language
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
∅ – there is nothing in the language, so the regular expression is
nothing as well
Problem 9
Explain why figure 9 is not a DFA
(Hint: It’s not because of the alphabet, nor is it because of the weird state names)
Not every node has the entire alphabet leaving from it, that alphabet being
{a, 0, 1}. Specifically q1 only has 1 coming out of it.
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 10
Explain why figure 10 is not a DFA
(Hint: it’s not because there are no
accept states, nor is it because the
state names are out of order).
You can go to two different states
through “c” from q0 (either back to
q0 or to c).
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
HW 04-02—-SOLUTION—- Finite Automata DFAs – USING JFLAP
EXAMPLE
Introductory Note: In the next problem (problem 11) I want to give you more practice converting from a regular
expression to a set so that before I get you to draw a DFA that matches a certain regular expression you take time to
understand what that regular expression really means, so I ask you to describe it both as a set as well as in English, and
then give 5 example strings that are in the language. Here is an example – my answers are in bold fuchsia
Example
For each of the regular expressions given below:
● Describe it as a set
● Describe it in English
● List 5 strings that are in that language
○ Unless there are fewer than 5, in that case just list them all
● List 5 strings that are not in that language but still use the same alphabet
○ Unless there are fewer than 5, in that case just list them all
● Make sure that lambda is included in one of the two lists above!
a*b + a*c + a*Λ
My example answer:
Set: {Λ, a, b, c, aa, ab, ac, aaa, aab, aac, aaaa, aaab, aaac, …}
(or you could answer {a}*{Λ, b,c} or {a}*{b} ∪ {a}*{c} ∪ {a}* or many other ways
English: 0 or more ‘a’ optionally followed by either a ‘b’ or a ‘c’ Examples of strings in language:
● Λ
● b
● c
● ab
● aaaac
● aaaaaaaaab
Examples of strings NOT in language:
● ba
● bb
● cc
● bab
● aaaabc
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 11 [Optional]
For each of the regular expressions given below:
● Describe it as a set
● Describe it in English
● List 5 strings that are in that language
○ Unless there are fewer than 5, in that case just list them all
● List 5 strings that are not in that language but still use the same alphabet
○ Unless there are fewer than 5, in that case just list them all
● Make sure that lambda is included in one of the two lists above!
a. a + b
As a set: {a, b}
In English: a or b
Strings in Language: a, b
Strings Not in Language: Λ, ab, ba, bb, aa
b. a + bc
As a set: {a, bc}
In English: a or bc
Strings in Language: a, bc
Strings Not in Language: Λ, ca, cc, c, b
c. a + b*
As a set: {a} U {bn | n ∈ N}
In English: a or any number of b’s
Strings in Language: Λ, a, b, bb, bbb
Strings Not in Language: aa, ab, ba, aaa, baaa
d. ab* + c
As a set: {abn | n ∈ N} U {c}
In English: a followed by any number of b’s, or c
Strings in Language: c, a, ab, abb, abbb
Strings Not in Language: Λ, ac, ca, cb, bc
e. ab* + bc*
As a set: {abn | n ∈ N} U {bcn | n ∈ N}
In English: a followed by any number of b’s, or b followed by any number of c’s
Strings in Language: a, b, ab, ac, abb, acc
Strings Not in Language: Λ, bc, bcc, ac, c
[optional] f. a*bc* + ac
As a set: {anbcm | n, m ∈ N} U {ac}
In English: any number of a’s followed by b followed by any number of c’s, or a followed by c
Strings in Language: b, ab, ac, bc, abc
Strings Not in Language: Λ, cba, acc, aba, bba
g. a*b*
As a set: {anbm | n, m ∈ N}
In English: any number of a’s followed by any number of b’s
Strings in Language: Λ, a, b, aa, ab
Strings Not in Language: aba, abba, ba, baa, bab
[optional] h. a* + b*
As a set: {bn | n ∈ N} U {an | n ∈ N}
In English: any number of a’s or any number of b’s
Strings in Language: Λ, a, b, aa, bb
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Strings Not in Language: ab, ba, bba, aba, abb
Problem 12
Use your wits to construct a DFA for each of the following regular expressions.
You should assume that the alphabets for each language are just whatever symbols that I used in that
question, e.g. assume the alphabet for the regular expression a+b is {a,b} and the alphabet for the regular
expression ab*+c is {a,b,c}
● Note1 – these are the same regular expressions you described in the previous problem!
● Note 2 – each of these subproblems should be done by creating DFAs in JFLAP. Do NOT include the
answer in your regular homework pdf, instead, each one should be included as a separate file in jff
format with names as specified in fuchsia below that you will add to the zip file you upload
● Note 3 – Make sure that when you build these they REALLY ARE DFAs. JFLAP won’t complain if you
have multiple outputs for the same letter from a single node, or forget to put outputs for all the letters
in a particular node, but I will!!
● Note 4 – Once you’ve made a machine, test it using the list of strings you created in problem 11
[optional] a. a + b ( Save as HW04_Problem12_a.jff )
[optional] b. a + bc ( Save as HW04_Problem12_b.jff )
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
[optional] c. a + b* ( Save as HW04_Problem12_c.jff )
d. ab* + c ( Save as HW04_Problem12_d.jff )
e. ab* + bc* ( Save as HW04_Problem12_e.jff )
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
f. a*bc* + ac( Save as HW04_Problem12_f.jff )
g. a*b*
( Save as HW04_Problem12_g.jff )
You should Test your jff file for a*b*
● Test it on the following cases:
● These should all be in the language:
○ Λ
○ a
○ b
○ aaaaa
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
●
○ bbbbbbb
○ aaaabbbbbbbbbbb
○ ab
These should NOT be in the language:
○ ba
○ aba
○ bbbba
○ aaaba
○ bbbbbba
○ aaaaaaaaaabaaaaaaa
h. a* + b*
( Save as HW04_Problem12_h.jff )
Note that I had to make q0 an accept state so I could accept lambda!!
Test your jff file on the following cases:
● These should all be in the language:
● Λ
● a
● b
● aaaaa
● bbbbbbb
● aa
● bb
●
● These should NOT be in the language:
○ ba
○ aba
○ bbbba
○ aaaba
○ bbbbbba
○ aaaaaaaaaabaaaaaaa
○ aaaabbbb
○ aabbbbbbbbbb
○ abbbbb
At this point, you should have a bunch of jflap files.
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
●
zip all the jflap files up into a single file called HW04-02_JFLAP_FILES.zip
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
HW 04-03—-SOLUTION—- Finite Automata NFAs without JFLAP
Problem 13
Answer all of the following questions for the
NFA shown in Figure 11
You do NOT need to specify the sequence
of states that you visit
a. Does it accept the string Λ yes
b. Does it accept the string a yes
c. Does it accept the string b yes
d. Does it accept the string c yes
e. Does it accept the string aa yes
f. Does it accept the string ab no
g. Does it accept the string bb yes
h. Does it accept the string bc no
i. Does it accept the string cc yes
j. Does it accept the string aaa yes
k. Does it accept the string bbb yes
l. Does it accept the string ccc yes
m. Does it accept the string aab no
n. Does it accept the string bbc no
o. Does it accept the string cca no
p. Does it accept the string abb no
q. Does it accept the string bcc no
r. Does it accept the string caa no
s. Does it accept the string abc no
Is the language of this NFA finite or infinite??
Infinite
Give a regular expression that represent what this NFA accepts
a*+b*+c*
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 14
Answer all of the following questions for the NFA shown in Figure 12 above
You do NOT need to specify the sequence of states that you visit
[a through s are optional]
a. Does it accept the string Λ Yes
b. Does it accept the string a Yes
c. Does it accept the string b Yes
d. Does it accept the string c Yes
e. Does it accept the string aa Yes
f. Does it accept the string ab Yes
g. Does it accept the string bb Yes
h. Does it accept the string bc Yes
i. Does it accept the string cc Yes
j. Does it accept the string aaa Yes
k. Does it accept the string bbb Yes
l. Does it accept the string ccc Yes
m. Does it accept the string aab Yes
n. Does it accept the string bbc Yes
o. Does it accept the string cca No
p. Does it accept the string abb Yes
q. Does it accept the string bcc Yes
r. Does it accept the string caa No
s. Does it accept the string abc Yes
Is the language of this NFA finite or infinite??
Infinite
[Optional] Give a set that represents what this NFA accepts
{anbmck |n, m, k ∈ ℕ}
Give a regular expression that represent what this NFA accepts
This NFA accepts all strings that have 0 or more a’s followed by 0 or more b’s followed by 0 or
more c’s so the regular expression is:
a*b*c*
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Problem 15
Answer all of the following questions for the NFA shown in Figure 13 above
You do NOT need to specify the sequence of states that you visit
[a through s are optional]
a. Does it accept the string Λ Yes
b. Does it accept the string a No
c. Does it accept the string b No
d. Does it accept the string c No
e. Does it accept the string aa No
f. Does it accept the string ab No
g. Does it accept the string bb No
h. Does it accept the string bc No
i. Does it accept the string cc No
j. Does it accept the string aaa No
k. Does it accept the string bbb No
l. Does it accept the string ccc No
m. Does it accept the string aab No
n. Does it accept the string bbc No
o. Does it accept the string cca No
p. Does it accept the string abb No
q. Does it accept the string bcc No
r. Does it accept the string caa No
s. Does it accept the string abc Yes
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.
Is the language of this NFA finite or infinite??
Infinite
[optional]Give a set that represents what this NFA accepts
{(abc)n | n ∈ ℕ}
Give a regular expression that represent what this NFA accepts
(abc)*
Problem 16
Answer all of the following questions for the DFA shown in Figure 11 above
You do NOT need to specify the sequence of states that you visit
[a through s are optional but you need to answer the other questions at
the bottom
a. Does it accept the string Λ Yes
b. Does it accept the string a Yes
c. Does it accept the string b Yes
d. Does it accept the string c Yes
e. Does it accept the string aa Yes
f. Does it accept the string ab Yes
g. Does it accept the string bb Yes
h. Does it accept the string bc Yes
i. Does it accept the string cc Yes
j. Does it accept the string aaa Yes
k. Does it accept the string bbb Yes
l. Does it accept the string ccc Yes
m. Does it accept the string aab Yes
n. Does it accept the string bbc Yes
o. Does it accept the string cca No
p. Does it accept the string abb Yes
q. Does it accept the string bcc Yes
r. Does it accept the string caa No
s. Does it accept the string abc No
Is the language of this NFA finite or infinite??
Infinite
[optional ]Give a set that represents what this NFA accepts
{(anbm)kcp | n, m, k, p ∈ ℕ}
Give a regular expression that represent what this NFA accepts
(a+b)*c*
Questions Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42020110
Solutions Copyright © 2024, Jennifer S. Kay kay@rowan.edu and Harper Anne
zappon37@students.rowan.edu
Permission is granted to students currently enrolled in Dr. Kay’s classes to print this out for personal use.
This work may NOT be reproduced or shared IN ANY OTHER WAY without written permission from the author.