Foundation of CS

HW 02-01 Graphs and TuplesProblem 01
For each of the following tuples, draw a picture of the graph it represents
A. ({a,b,c,d,e}, {{a,b},{c,d}, {e,a}, {d,e}})
B. ({a,b,c,d,e}, {(a,a), (a,b), (d,e), (e,d) })
C. ({a,b,c,d,e,f,g}, {})
Problem 02
[optional]
Express the undirected graph below in the form G=(V,E)
Be very careful about where you put curly braces { } and where you put parentheses ( )
Problem 03
Express the directed graph below in the form G=(V,E)
Be very careful about where you put curly braces { } and where you put parentheses ( )
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 04
Express the undirected graph below in the form G=(V,E)
Be very careful about where you put curly braces { } and where you put parentheses ( )
1
2
3
4
5
Problem 05 [optional]
Express the directed graph below in the form G=(V,E)
Be very careful about where you put curly braces { } and where you put parentheses ( )
1
2
3
4
5
Figure 02
Problem 02-01-EX01
For each of the following – State whether it’s an Undirected Graph, a Directed Graph or Neither.
A.
B.
C.
D.
E.
F.
G.
H.
I.
( (a, b, c), ((a,b),(a,c)) )
( (a, b, c), {(a,b),(a,c)} )
( (a, b, c), ({a,b},{a,c}) )
( (a, b, c), {{a,b},{a,c}} )
( {a, b, c}, ((a,b),(a,c)) )
( {a, b, c}, {(a,b),(a,c)} )
( {a, b, c}, ({a,b},{a,c}) )
( {a, b, c}, {{a,b},{a,c}} )
{ (a, b, c), ((a,b),(a,c)) }
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.
J.
K.
L.
M.
N.
O.
P.
{ (a, b, c), {(a,b),(a,c)} }
{ (a, b, c), ({a,b},{a,c}) }
{ (a, b, c), {{a,b},{a,c}} }
{ {a, b, c}, ((a,b),(a,c)) }
{ {a, b, c}, {(a,b),(a,c)} }
{ {a, b, c}, ({a,b},{a,c}) }
{ {a, b, c}, {{a,b},{a,c}} }
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 02-02 Strings, Languages, and Alphabets
Notation
Important note: Strictly speaking, anything can be a symbol in an alphabet. Indeed, you will sometimes see me using
symbols like
or
in an alphabet, for example, I might say that A is an alphabet with 3 symbols and A = {a, b,
}.
However, for the purposes of this class, we have some special symbols that we will never use as elements of alphabets:
𝚲
Capital lambda is a special symbol which will always mean the empty string
Remember that 𝚲 is NEVER a symbol in an alphabet
(but you can just use it in strings or languages whenever you feel like it!)
∅
This is a special symbol which will always represent the empty set (it’s just a
shorthand for two curly braces: { }
Groups of English We use individual English letters as symbols all the time – here’s an example of
Letters
an alphabet with 3 symbols: {a, b, c}.
We will never squish multiple English letters together to represent a single
symbol – so, for example, the following is definitely NOT an alphabet:
{a, bc}
Because “bc” is a string of two symbols together.
Normal set and
tuple symbols
Things like parentheses, curly braces, and commas will always mean what you
think they mean – we’ll never say “oh, let’s talk about the alphabet that has just
one symbol – a comma – in it” – that would get too confusing.
Problem 06
Write down the set of all possible strings of length 2 over the set A = {a, b, c}.
Problem 07
Let L = {Λ, abb, b} and M = {bba, ab, a}. Evaluate each of the following language expressions.
[optional] a. LM
b. ML
c. L0
d. L1
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.
e. L2
Problem 08
Use your wits (i.e. just figure it out somehow…) to solve each of the following language equations for the
unknown language.
a. {Λ, a, ab} L = {b, ab, ba, aba, abb, abba}
Tip: this is saying that when you “multiply out” the set {Λ, a, ab} with the set represented by L,
you get the set {b, ab, ba, aba, abb, abba} and is asking “What is L?”
b. L {a, b} = {a, baa, b, bab}.
c. {a, aa, ab} L = {ab, aab, abb, aa, aaa, aba}.
d. L {Λ, a} = {Λ, a, b, ab, ba, aba}.
[optional]e. {a, b} L = {a, b, aba, bba}.
[optional]f. L {b, Λ, ab} = {abb, ab, abab, bab, b, bb}.
Problem EXTRA – 09
Explain why {a, b, c} could be an alphabet, but {𝝠, a,b,c) , abc, {abc} ,
{a, aa, aaa, aaaa, …. }, and (abc) could not
Problem New – 10
Could each of the following be Alphabets? Circle or highlight the correct answer
A. 𝝠
YES / NO
B. (𝝠)
YES / NO
C. {𝝠}
YES / NO
D. a, b, c
YES / NO
E. abc
YES / NO
F. {a,b,c}
YES / NO
G. (a,b,c)
YES / NO
H. (abc)
YES / NO
I.
{abc}
YES / NO
J. {𝝠, abc}
YES / NO
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.
K. {𝝠, a,b,c}
YES / NO
Problem New – 11
Could each of the following be Strings? Circle or highlight the correct answer
A. 𝝠
YES / NO
B. (𝝠)
YES / NO
C. {𝝠}
YES / NO
D. a, b, c
YES / NO
E. abc
YES / NO
F. {a,b,c}
YES / NO
G. (a,b,c)
YES / NO
H. (abc)
YES / NO
I.
{abc}
YES / NO
J. {𝝠, abc}
YES / NO
K. {𝝠, a,b,c}
YES / NO
Problem 12
● What is |Rowan Rocks|?
○ (Note – those bars are there on purpose!)
○ (Note – the space character has a length of 1, in contrast to 𝝠 which has a length of 0)
● What about |{Rowan, Rocks}|?
● What about |{R,o,w,a,n,c,k,s}| ?
[optional] Problem 13 List all the strings of length