NFAs and DFAs Questions

you have to follow the introduction and here’s the video link

HW 04-01 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)*
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Λ
ii.
Does it accept the string a
iii.
Does it accept the string b
iv.
Does it accept the string ab
v.
Does it accept the string ba
vi.
Does it accept the string aa
vii.
Does it accept the string bb
viii.
Does it accept the string aaa
ix.
Does it accept the string aab
x.
Does it accept the string aba
xi.
Does it accept the string abb
xii.
Does it accept the string baa
xiii.
Does it accept the string bab
xiv.
Does it accept the string bba
xv.
Does it accept the string bbb
b. Is the language of this DFA finite or infinite??
c. [optional] Give a set that represents what this DFA accepts
d. Give a regular expression that represents what this DFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Λ
Does it accept the string a
Does it accept the string b
Does it accept the string ab
Does it accept the string ba
Does it accept the string aa
Does it accept the string bb
Does it accept the string aaa
Does it accept the string aab
Does it accept the string aba
Does it accept the string abb
Does it accept the string baa
Does it accept the string bab
Does it accept the string bba
Does it accept the string bbb
Is the language of this DFA finite or infinite??
g. [optional] Give a set that represents what this DFA accepts
h. Give a regular expression that represent what this DFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Λ
Does it accept the string a
Does it accept the string b
Does it accept the string ab
Does it accept the string ba
Does it accept the string aa
Does it accept the string bb
Does it accept the string aaa
Does it accept the string aab
Does it accept the string aba
Does it accept the string abb
Does it accept the string baa
Does it accept the string bab
Does it accept the string bba
Does it accept the string bbb
i.
Is the language of this DFA finite or infinite??
j.
Give a set that represents what this DFA accepts
k. [optional] Give a regular expression that represent what this DFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 4
[i through xv are optional!!,
l.
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 Λ
ii.
Does it accept the string 0
iii.
Does it accept the string 1
iv.
Does it accept the string 00
v.
Does it accept the string 01
vi.
Does it accept the string 10
vii.
Does it accept the string 11
viii.
Does it accept the string 000
ix.
Does it accept the string 001
x.
Does it accept the string 010
xi.
Does it accept the string 011
xii.
Does it accept the string 100
xiii.
Does it accept the string 101
xiv.
Does it accept the string 110
xv.
Does it accept the string 111
m. Is the language of this DFA finite or infinite??
n. Give a regular expression that represents what this DFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 5
a. What is the set accepted by the DFA in figure 5?
b. Give a regular expression that represents that language
Problem 6
a. What is the set accepted by the DFA in figure 6?
b. Give a regular expression that represents that language
Problem 7
a. What is the set accepted by the DFA in figure 7?
b. Give a regular expression that represents that language
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 8
a. [optional]What is the set accepted by the DFA in figure 8 (Yes, this is a DFA!!) ?
b. Give a regular expression that represents that language
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)
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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).
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Finite Automata DFAs – USING JFLAP
Important Reminder:
Before doing this part of the homework, you MUST watch the following videos:
●
●
●
Foundations 05-02 JFLAP Creating DFAs and Stepping through Strings (21 mins)
Foundations 05-03 JFLAP IMPORTANT WARNING (5 mins)
Foundations 05-04 JFLAP processing multiple strings (4 mins)
Notes on What to Submit:
When you save a jflap file, it will get a jff extension. In previous weeks you have only uploaded pdf files for your
homework. This week you will:
● create a pdf file of all your non-JFLAP-homework (OK to have two separate pdf files)
● create a bunch of individual JFLAP files for the problems that ask you to use jflap
● upload your one or two pdf files and ALL of your JFLAP files (in numerical order please!) into the
assignment on Canvas
Additional Notes
●
●
●
Start symbol: From now on, you may choose to draw the start symbol for a Finite Automaton as the
book does it (an arrow with the word start) or as a triangle like JFLAP does it.
Lambda: From now on, you can draw lambda as a lower or upper case lambda. I’ll continue to do
upper case lambda (Λ) when I hand-draw FAs and lower-case lambda (λ) when I create FAs in JFLAP.
Commas: Remember: you must NEVER use commas for DFAs or NFAs in JFLAP . You may
continue to use things like “a,b” on a transition on a hand-drawn DFA or NFA, but NEVER IN JFLAP!!
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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.
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
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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
b. a + bc
c. a + b*
d. ab* + c
e. ab* + bc*
f. a*bc* + ac
g. a*b*
h. a* + b*
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 )
[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 )
f. a*bc* + ac( Save as HW04_Problem12_f.jff )
g. a*b*
( Save as HW04_Problem12_g.jff )
h. a* + b*
( Save as HW04_Problem12_h.jff )
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Finite Automata NFAs without JFLAP
Reminders on What to Submit:
When you save a jflap file, it will get a jff extension. In previous weeks you have only uploaded pdf files for your
homework. This week you will:
● create a pdf file of all your non-JFLAP-homework (OK to have two separate pdf files)
● create a bunch of individual JFLAP files for the problems that ask you to use jflap
● upload your one or two pdf files and ALL of your JFLAP files (in numerical order please!) into the
assignment on Canvas
Additional Notes
●
●
●
Start symbol: From now on, you may choose to draw the start symbol for a Finite Automaton as the
book does it (an arrow with the word start) or as a triangle like JFLAP does it.
Lambda: From now on, you can draw lambda as a lower or upper case lambda. I’ll continue to do
upper case lambda (Λ) when I hand-draw FAs and lower-case lambda (λ) when I create FAs in JFLAP.
Commas: Remember: you must NEVER use commas for DFAs or NFAs in JFLAP . You may
continue to use things like “a,b” on a transition on a hand-drawn DFA or NFA, but NEVER IN JFLAP!!
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 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 Λ
b. Does it accept the string a
c. Does it accept the string b
d. Does it accept the string c
e. Does it accept the string aa
f. Does it accept the string ab
g. Does it accept the string bb
h. Does it accept the string bc
i. Does it accept the string cc
j. Does it accept the string aaa
k. Does it accept the string bbb
l. Does it accept the string ccc
m. Does it accept the string aab
n. Does it accept the string bbc
o. Does it accept the string cca
p. Does it accept the string abb
q. Does it accept the string bcc
r. Does it accept the string caa
s. Does it accept the string abc
Is the language of this NFA finite or infinite??
Give a regular expression that represent what this NFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Λ
b. Does it accept the string a
c. Does it accept the string b
d. Does it accept the string c
e. Does it accept the string aa
f. Does it accept the string ab
g. Does it accept the string bb
h. Does it accept the string bc
i. Does it accept the string cc
j. Does it accept the string aaa
k. Does it accept the string bbb
l. Does it accept the string ccc
m. Does it accept the string aab
n. Does it accept the string bbc
o. Does it accept the string cca
p. Does it accept the string abb
q. Does it accept the string bcc
r. Does it accept the string caa
s. Does it accept the string abc
Is the language of this NFA finite or infinite??
[Optional] Give a set that represents what this NFA accepts
Give a regular expression that represent what this NFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 Λ
b. Does it accept the string a
c. Does it accept the string b
d. Does it accept the string c
e. Does it accept the string aa
f. Does it accept the string ab
g. Does it accept the string bb
h. Does it accept the string bc
i. Does it accept the string cc
j. Does it accept the string aaa
k. Does it accept the string bbb
l. Does it accept the string ccc
m. Does it accept the string aab
n. Does it accept the string bbc
o. Does it accept the string cca
p. Does it accept the string abb
q. Does it accept the string bcc
r. Does it accept the string caa
s. Does it accept the string abc
Is the language of this NFA finite or infinite??
[optional]Give a set that represents what this NFA accepts
Give a regular expression that represent what this NFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 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 Λ
b. Does it accept the string a
c. Does it accept the string b
d. Does it accept the string c
e. Does it accept the string aa
f. Does it accept the string ab
g. Does it accept the string bb
h. Does it accept the string bc
i. Does it accept the string cc
j. Does it accept the string aaa
k. Does it accept the string bbb
l. Does it accept the string ccc
m. Does it accept the string aab
n. Does it accept the string bbc
o. Does it accept the string cca
p. Does it accept the string abb
q. Does it accept the string bcc
r. Does it accept the string caa
s. Does it accept the string abc
Is the language of this NFA finite or infinite??
[optional ]Give a set that represents what this NFA accepts
Give a regular expression that represent what this NFA accepts
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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-04 Finite Automata NFAs – USING JFLAP
Important Reminder:
Before doing this part of the homework, you MUST watch the following videos:
●
●
●
●
Foundations 05-06 JFLAP add trash state to DFA (4 mins)
Foundations 05-07 JFLAP – NFA Step by State (15 mins)
Foundations 05-08 JFLAP – NFA Step by Closure (8 mins)
Foundations 05-09 JFLAP – NFAs Running Multiple Examples (2 mins)
Notes on What to Submit:
When you save a jflap file, it will get a jff extension. In previous weeks you have only uploaded pdf files for your
homework. This week you will:
● create a pdf file of all your non-JFLAP-homework (OK to have two separate pdf files)
● create a bunch of individual JFLAP files for the problems that ask you to use jflap
● upload your one or two pdf files and ALL of your JFLAP files (in numerical order please!) into the
assignment on Canvas
Additional Notes
●
●
●
Start symbol: From now on, you may choose to draw the start symbol for a Finite Automaton as the
book does it (an arrow with the word start) or as a triangle like JFLAP does it.
Lambda: From now on, you can draw lambda as a lower or upper case lambda. I’ll continue to do
upper case lambda (Λ) when I hand-draw FAs and lower-case lambda (λ) when I create FAs in JFLAP.
Commas: Remember: you must NEVER use commas for DFAs or NFAs in JFLAP . You may
continue to use things like “a,b” on a transition on a hand-drawn DFA or NFA, but NEVER IN JFLAP!!
Problem 17
Use your wits to construct an NFA for each of the following regular expressions.
Note1 – these are the same regular expressions you described in the problem 11!
Note 2 – each of these subproblems should be done by creating NFAs from scratch in JFLAP. (Yes, strictly
speaking, your answers to part 12 would be fine here since all DFAs are NFAs, but I want you to see how
much easier these are!!!)
Note 3: each of these subproblems should be done by creating NFAs 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
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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.
Note 4 – Once you’ve made a machine, be sure to test it!
Consider using the list of strings you created in problem 11
[optional] a. a + b. ( Save as HW04_Problem17_a.jff )
[optional] b. a + bc. ( Save as HW04_Problem17_b.jff )
[optional] c. a + b*. ( Save as HW04_Problem17_c.jff )
d. ab * + c. ( Save as HW04_Problem17_d.jff )
e. ab* + bc*. ( Save as HW04_Problem17_e.jff )
f. a*bc* + ac.( Save as HW04_Problem17_f.jff )
g. a*b*. (Hint – in my solution EVERY state is an accept state!)
( Save as HW04_Problem17_g.jff )
h. a* + b*. (Hint – in my solution EVERY state is an accept state!)
( Save as HW04_Problem17_h.jff )
Problem 18
Use your wits to construct an NFA in JFLAP that accepts the language that accepts all strings over the alphabet {a,b,c,d}
that start with an a and end with a d.
Hint: after you’re done double check that you covered everything in the given alphabet
Note: Do NOT include the answer in your regular homework pdf, instead,Note: Do NOT include the answer in your
regular homework pdf, instead, it 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 uploadHW04_problem18.jff
Problem 19
Use your wits to construct an NFA in JFLAP that accepts the language that accepts all strings over the
alphabet {a,b,c,d} that contain at least one a and one b. So, for example, the following strings are in the
language:
● ab
● ba
● abcd
● acbddddaaa
● bbbbbdddddda
● cccccbcccaccccc
and the following strings are not in the language:
a. a
b. b
c. aaaccd
d. d
e. c
f. cccbccc
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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.
Hint: after you’re done double check that you covered everything in the given alphabet and that
you can have the b and a in any order.
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include
the answer in your regular homework pdf, instead, it 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
HW04_problem19.jff
Problem 20
Use JFLAP to create an NFA that accepts:
The set of all strings over the alphabet {a, b, c} that start with the substring bc
So, for example, the following strings are in the language:
● bc, bca, bcc, bcbc, bcbcbc, bcaaaaaa, bcbbbb, bccb
And the following strings are not in the language:
● bac, cbca, bbbccc, abc, aaabc, aababa
●
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT
include the answer in your regular homework pdf, instead, it 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
HW04_problem.jff
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 21
Use JFLAP to create an NFA that accepts:
The set of all strings over the alphabet {a, b, c} that always contain the substring “bc” (at least one or
more times)
So, for example, the following strings are in this language:
g. bc, abc, aaaaaaaaabc, abcba, bc, bcb, aaaabcaaacbc, bbc, bcabc
and the following strings are NOT in this language:
h. cb, acb, aaaa, bbbb, c, b, a, bronco, cccccccccccccabac
i.
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include
the answer in your regular homework pdf, instead, it 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
HW04_Problem21.jff
Problem 22
Use JFLAP to create an NFA that accepts:
The set of all strings over the alphabet {a, b, c, d} that contain exactly one a and exactly one b
So, for example, the following strings are in this language:
● ab, ba, cccbad, acbd, cabddddd, ddbdddacccc
and the following strings are NOT in this language:
● a, ccbc, acbcaaacba, acacac, bcbbbbbca, aca, c, d, b
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include
the answer in your regular homework pdf, instead, it 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
●
HW04_Problem22.jff
Problem 23
Use JFLAP to create an NFA that accepts the language L where:
L = The set of strings over the alphabet {a, b, c, d} where every “c” is immediately preceded and also
followed by a “b” (i.e. every “c” has the symbol “b” right next to it on both sides) So, for example …
These strings are in L:
j. a, b, d, bcb, bcbcb, abbbbcbddabcb, abd, dbcbcb,
and these strings are NOT in L:
k. abc, abcbabc, asdc, cbbb, acb
l.
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include
the answer in your regular homework pdf, instead, it 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
HW04_Problem23.jff
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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 24 [optional but encouraged]
Use JFLAP to create an NFA that accepts the language M where:
M = the set of strings over the alphabet {a,b,c,d} which start with the letter ‘a’ or the letter ‘b’ and also contain exactly
one c
For example, the following strings are in M:
● ac, bc, abc, abcba, bcbd, bbbbbbc, aaaaaabbbbcdd, bbbbcaaa
and these are NOT in M:
m. abcbabc, a, b, c, d, ca, dbbbacbba, bcabcd
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include
the answer in your regular homework pdf, instead, it 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
n. HW04_Problem24.jff
[optional] Problem 25
Use JFLAP to create an NFA that accepts:
The set of all strings over the alphabet {a,b,c} such that no string contains the substring aaa.
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include the answer in your
regular homework pdf, instead, it 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 HW04_Problem25.jff
problem 26 Use JFLAP to create an NFA that accepts:
The set of all strings over the alphabet {a,b,c} such that no string contains the substring aa.
Note: Do NOT include the answer in your regular homework pdf, instead, Note: Do NOT include the answer in your
regular homework pdf, instead, it 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 uploadHW04_Problem26.jff
Assignment Submission Instructions
At this point, you should have a single pdf file (for all 4 parts of this homework) and a bunch of jflap files.
● zip all the jflap files up into a single file called HW04_JFLAP_FILES.zip
● Upload 2 files – your pdf and your zip
Copyright © 2024, Jennifer S. Kay, kay@rowan.edu
v. 42028010
Permission is granted to students currently enrolled in my 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.