USA: +1(669)289-8683 
Sign in
Updated February 27, 2022COSC 2425 S22
Program Set #2
Total Points: 30
Three problems must be implemented for full credit. Each section will state how many problems to
implement within it. The required (starred) problem marked in the set must be implemented by
everyone. See the 2425 Grading and Submission Guide Sheets for additional grading/submission
information. Partial credit will be given. (10 points each)
Note: If coding in C++, use the STL string class for the problems below involving strings. Do not use C
style strings.
Section One- Choose two problems.
1. Write a program to simplify a Boolean expression. The user will enter from the keyboard a string
representing a valid Boolean expression with spaces between the letters. The operators used will be OR
(+), AND (*) and NOT (~), and the only valid Input characters will be A, B, +, *, ~, ( , ), 1 and 0.
The expression will contain at most 3 operands, 3 operators and one set of parentheses. Output to the
screen a line printing the simplified equivalent of the given expression. Simplify means outputting the
fewest operators with no parentheses. Use the following list of Boolean Identities to simplify:
Refer to the sample output below.
Sample Runs (2):
Enter a string: ~(A + B)
Simplified expression: ~A * ~B
Enter a string: ~A * A + 1
1
Updated February 27, 2022
COSC 2425 S22
Simplified expression: 1
Name the program: BoolSimplifyXX.cpp or BoolSimplifyXX.java, where XX are your initials.
2. Write a program that given a transition table representing a regular expression of an FSA (Finite State
Automata) outputs the regular expression. For example:
State/Rule
1
2
3
a
2
3
0
b
0
2
0
The regular expression from the above table is: ab*a. If a bit can be either a 1 or a 0 then represent
that bit with a *. The table has been simplified so that a*a and b*b will never be part of a path. Input
will be from the keyboard. The first line will be the number of states in the FSA. The next line will contain
the states that will fill the first column of the table in order from 1 to n. The input data will be in the
form of 2-character strings representing each row of the transition table. The first character tells if a
path exits using transition rule “a”. The second character tells if a path exits using transition rule “b”.
Separate each ab value with a space. Assume proper input. For each input, output to the screen the
appropriate regular expression. Parentheses are not needed. Refer to the sample output below.
Sample Runs (2):
Enter the number of FSA states: 3
Enter the table data: 20 32 00
Equivalent regular expression: ab*a
Enter the number of FSA states: 4
Enter the table data: 12 32 04 00
Equivalent regular expression: a*bb*ab
Name the program: RegExpressionXX.cpp or RegExpressionXX.java, where XX are your initials.
3. Karnaugh Maps are a tool for finding the Boolean expression that produces a truth table for
simplifying the expression. Write a program that simplifies a given Boolean function by using a Karnaugh
Map (K-map). Allow the user to enter the number of variables and a Boolean function from sigma Sum
of Product (SOP) notation. For example:
F (A, B, C, D) = ∑ m (0,2,3,5,6,7,8,10,11,14,15)
2
Updated February 27, 2022
COSC 2425 S22
shows where the terms (locations) evaluate to 1 (true). So, at the following locations in the 4 x 4
matrix: 0,2,3,5,6,7,8,10,11,14,15 input a 1 and the remaining locations would be filled with
zeros.
Display a 2, 3, or 4 variable Karnaugh Map for the function entered. The values in the matrices below are
locations using Gray code (decimal notation). Use A, B, C, or D as the variable names depending on the
size.
The rules for simplification with a K-map are as follows:
• Each group should contain the largest number of ‘ones’ (1s) and no blank cells.
• The number of ‘ones’ in a group must be a power of 2
• Grouping is carried-on in decreasing order meaning, one must try to group for 8 (octet) first,
then for 4 (quad), followed by 2 and lastly for 1 (isolated ‘ones’).
• Grouping is done either horizontally or vertically or in terms of rectangles/squares. Diagonal
grouping of ‘ones’ is not permitted.
• The same element(s) may repeat in multiple groups only if this increases the size of the group.
• The elements around the edges of the matrix, including the four corners, are considered
adjacent and can be grouped together.
Output to the screen the initial contents of the K-map. After simplification, the program should print
the decimal notation of each group simplified and the Boolean function for each input. Finally, output
the combined simplified Boolean expression written with capital letters in the format as seen below. Do
not worry about don’t care conditions. Refer to the sample output below.
3
Updated February 27, 2022
COSC 2425 S22
Sample Run:
Enter the number of variables: 4
Enter the location of the 1 values: 0 2 3 5 6 7 8 10 11 14 15
========K Map=========
\AB|
CD \ | 00 01 11 10
—–+—————00 | 1 | 0 | 0 | 1 |
—–+—+—+—+—01 | 0 | 1 | 0 | 0 |
—–+—+—+—+—11 | 1 | 1 | 1 | 1 |
—–+—+—+—+—10 | 1 | 1 | 1 | 1 |
———————Group 1: 2 3 6 7 10 11 14 15
Simplification of group 1 -> C
Group 2: 0 2 8 10
Simplification of group 2 -> B’D’
Group 3: 5 7
Simplification of group 3 -> A’BD
F(A,B,C,D) = C + B’D’ + A’BD
Name the program: KMapXX.cpp or KMapXX.java, where XX are your initials.
Required Problem- Comprehensive.
4. (**). In the simple application of error checking in message transmission, a sender transmits a
message, a key, and a checksum. The receiver of the message divides the message by the key and
determines if the remainder matches the checksum sent. If all the message parts are converted to
binary, then the division in modulo 2 is equivalent to the long division algorithm except rather than
subtracting the bits, they are XORed. The following example demonstrates the algorithm:
000010011000 ÷ 0101
000010011000
101
111
101
100
101
100
101
01
4
Updated February 27, 2022
COSC 2425 S22
Note only the remainder after the XOR process is important, and the final remainder is always expressed
using the number of significant bits in the key, minus 1. In the example above, since the key 0101 has
three significant digits (leading zeros do not count), the final remainder must be expressed in two
significant digits, or 01. Write a program to demonstrate the Cyclic Redundancy Check (CRC) algorithm
as stated above. Input from the keyboard a pair of hex values on one line, the message, and the key,
separated by a single space. Assume proper input. For each pair of input values, calculate and output to
the screen the final checksum. Refer to the sample output below.
Sample Runs (2):
Enter two hex values separated by a space: 098 5
CRC Checksum: 01
Enter two hex values separated by a space: AC 5
CRC Checksum: 11
Name the program: CRCSumXX.cpp or CRCSumXX.java, where XX are your initials.
5
Updated February 27, 2022
COSC 2425 S22
Extra Credit: Implement the following problem. See the 2425 Grading and Submission Guide Sheets
for additional grading/submission information. Partial credit will be given. (10 points)
Write a program that given a truth table, outputs the Boolean expression it represents. For example:
Column:
1
2
3
4
5
A
0
0
1
1
B
0
1
0
1
A OR B
0
1
1
1
A AND B
0
0
0
1
XOR
0
1
1
0
Given two inputs (A B) that are represented by columns 1 and 2 and that column 3 is evaluated by an
operation on columns 1 and 2, it can be determined that the operation must be an OR. Therefore,
column 3 is (A OR B). If column 4 is evaluated using columns 1 and 2, it is (A AND B). If column 5 is
found by operations on columns 3 and 4, the operation is XOR. Therefore, the overall Boolean
expression is:
((A OR B) XOR (A AND B))
To avoid any problems caused by the lack of uniqueness check the operations and use the first
occurrence in the following order: AND, OR, XOR, NAND, NOR and XNOR. Input will be from a data file.
The first line will contain the number of values in the file. For each value, one line will contain the
number of variables, the number of operations, strings representing the outcomes of the operations
across the rows, and the two-character strings representing, in order, the columns used in each
operation. Output to the screen the Boolean expression properly labeled. Although the commutative
property applies, output the answer in the order implied by the given column numbers. Also, all twoterm operations must be outputted using parentheses as shown below. Let the user input the file name
from the keyboard. Refer to the sample output below.
Sample File:
3
2 2 00 01 00 11 12 23
2 2 01 10 11 00 12 13
2 3 000 101 101 110 12 12 34
Sample Run:
Enter file name: values.txt
Set 1: (B OR (A AND B))
Set 2: (A XNOR (A XOR B))
Set 3: ((A OR B) XOR (A AND B))
Name the program: BoolExpressXX.cpp or BoolExpressXX.java, where XX are your initials.
6
Updated February 27, 2022
COSC 2425 S22
Program Set #2
Total Points: 30
Three problems must be implemented for full credit. Each section will state how many problems to
implement within it. The required (starred) problem marked in the set must be implemented by
everyone. See the 2425 Grading and Submission Guide Sheets for additional grading/submission
information. Partial credit will be given. (10 points each)
Note: If coding in C++, use the STL string class for the problems below involving strings. Do not use C
style strings.
Section One- Choose two problems.
1. Write a program to simplify a Boolean expression. The user will enter from the keyboard a string
representing a valid Boolean expression with spaces between the letters. The operators used will be OR
(+), AND (*) and NOT (~), and the only valid Input characters will be A, B, +, *, ~, ( , ), 1 and 0.
The expression will contain at most 3 operands, 3 operators and one set of parentheses. Output to the
screen a line printing the simplified equivalent of the given expression. Simplify means outputting the
fewest operators with no parentheses. Use the following list of Boolean Identities to simplify:
Refer to the sample output below.
Sample Runs (2):
Enter a string: ~(A + B)
Simplified expression: ~A * ~B
Enter a string: ~A * A + 1
1
Updated February 27, 2022
COSC 2425 S22
Simplified expression: 1
Name the program: BoolSimplifyXX.cpp or BoolSimplifyXX.java, where XX are your initials.
2. Write a program that given a transition table representing a regular expression of an FSA (Finite State
Automata) outputs the regular expression. For example:
State/Rule
1
2
3
a
2
3
0
b
0
2
0
The regular expression from the above table is: ab*a. If a bit can be either a 1 or a 0 then represent
that bit with a *. The table has been simplified so that a*a and b*b will never be part of a path. Input
will be from the keyboard. The first line will be the number of states in the FSA. The next line will contain
the states that will fill the first column of the table in order from 1 to n. The input data will be in the
form of 2-character strings representing each row of the transition table. The first character tells if a
path exits using transition rule “a”. The second character tells if a path exits using transition rule “b”.
Separate each ab value with a space. Assume proper input. For each input, output to the screen the
appropriate regular expression. Parentheses are not needed. Refer to the sample output below.
Sample Runs (2):
Enter the number of FSA states: 3
Enter the table data: 20 32 00
Equivalent regular expression: ab*a
Enter the number of FSA states: 4
Enter the table data: 12 32 04 00
Equivalent regular expression: a*bb*ab
Name the program: RegExpressionXX.cpp or RegExpressionXX.java, where XX are your initials.
3. Karnaugh Maps are a tool for finding the Boolean expression that produces a truth table for
simplifying the expression. Write a program that simplifies a given Boolean function by using a Karnaugh
Map (K-map). Allow the user to enter the number of variables and a Boolean function from sigma Sum
of Product (SOP) notation. For example:
F (A, B, C, D) = ∑ m (0,2,3,5,6,7,8,10,11,14,15)
2
Updated February 27, 2022
COSC 2425 S22
shows where the terms (locations) evaluate to 1 (true). So, at the following locations in the 4 x 4
matrix: 0,2,3,5,6,7,8,10,11,14,15 input a 1 and the remaining locations would be filled with
zeros.
Display a 2, 3, or 4 variable Karnaugh Map for the function entered. The values in the matrices below are
locations using Gray code (decimal notation). Use A, B, C, or D as the variable names depending on the
size.
The rules for simplification with a K-map are as follows:
• Each group should contain the largest number of ‘ones’ (1s) and no blank cells.
• The number of ‘ones’ in a group must be a power of 2
• Grouping is carried-on in decreasing order meaning, one must try to group for 8 (octet) first,
then for 4 (quad), followed by 2 and lastly for 1 (isolated ‘ones’).
• Grouping is done either horizontally or vertically or in terms of rectangles/squares. Diagonal
grouping of ‘ones’ is not permitted.
• The same element(s) may repeat in multiple groups only if this increases the size of the group.
• The elements around the edges of the matrix, including the four corners, are considered
adjacent and can be grouped together.
Output to the screen the initial contents of the K-map. After simplification, the program should print
the decimal notation of each group simplified and the Boolean function for each input. Finally, output
the combined simplified Boolean expression written with capital letters in the format as seen below. Do
not worry about don’t care conditions. Refer to the sample output below.
3
Updated February 27, 2022
COSC 2425 S22
Sample Run:
Enter the number of variables: 4
Enter the location of the 1 values: 0 2 3 5 6 7 8 10 11 14 15
========K Map=========
\AB|
CD \ | 00 01 11 10
—–+—————00 | 1 | 0 | 0 | 1 |
—–+—+—+—+—01 | 0 | 1 | 0 | 0 |
—–+—+—+—+—11 | 1 | 1 | 1 | 1 |
—–+—+—+—+—10 | 1 | 1 | 1 | 1 |
———————Group 1: 2 3 6 7 10 11 14 15
Simplification of group 1 -> C
Group 2: 0 2 8 10
Simplification of group 2 -> B’D’
Group 3: 5 7
Simplification of group 3 -> A’BD
F(A,B,C,D) = C + B’D’ + A’BD
Name the program: KMapXX.cpp or KMapXX.java, where XX are your initials.
Required Problem- Comprehensive.
4. (**). In the simple application of error checking in message transmission, a sender transmits a
message, a key, and a checksum. The receiver of the message divides the message by the key and
determines if the remainder matches the checksum sent. If all the message parts are converted to
binary, then the division in modulo 2 is equivalent to the long division algorithm except rather than
subtracting the bits, they are XORed. The following example demonstrates the algorithm:
000010011000 ÷ 0101
000010011000
101
111
101
100
101
100
101
01
4
Updated February 27, 2022
COSC 2425 S22
Note only the remainder after the XOR process is important, and the final remainder is always expressed
using the number of significant bits in the key, minus 1. In the example above, since the key 0101 has
three significant digits (leading zeros do not count), the final remainder must be expressed in two
significant digits, or 01. Write a program to demonstrate the Cyclic Redundancy Check (CRC) algorithm
as stated above. Input from the keyboard a pair of hex values on one line, the message, and the key,
separated by a single space. Assume proper input. For each pair of input values, calculate and output to
the screen the final checksum. Refer to the sample output below.
Sample Runs (2):
Enter two hex values separated by a space: 098 5
CRC Checksum: 01
Enter two hex values separated by a space: AC 5
CRC Checksum: 11
Name the program: CRCSumXX.cpp or CRCSumXX.java, where XX are your initials.
5
Updated February 27, 2022
COSC 2425 S22
Extra Credit: Implement the following problem. See the 2425 Grading and Submission Guide Sheets
for additional grading/submission information. Partial credit will be given. (10 points)
Write a program that given a truth table, outputs the Boolean expression it represents. For example:
Column:
1
2
3
4
5
A
0
0
1
1
B
0
1
0
1
A OR B
0
1
1
1
A AND B
0
0
0
1
XOR
0
1
1
0
Given two inputs (A B) that are represented by columns 1 and 2 and that column 3 is evaluated by an
operation on columns 1 and 2, it can be determined that the operation must be an OR. Therefore,
column 3 is (A OR B). If column 4 is evaluated using columns 1 and 2, it is (A AND B). If column 5 is
found by operations on columns 3 and 4, the operation is XOR. Therefore, the overall Boolean
expression is:
((A OR B) XOR (A AND B))
To avoid any problems caused by the lack of uniqueness check the operations and use the first
occurrence in the following order: AND, OR, XOR, NAND, NOR and XNOR. Input will be from a data file.
The first line will contain the number of values in the file. For each value, one line will contain the
number of variables, the number of operations, strings representing the outcomes of the operations
across the rows, and the two-character strings representing, in order, the columns used in each
operation. Output to the screen the Boolean expression properly labeled. Although the commutative
property applies, output the answer in the order implied by the given column numbers. Also, all twoterm operations must be outputted using parentheses as shown below. Let the user input the file name
from the keyboard. Refer to the sample output below.
Sample File:
3
2 2 00 01 00 11 12 23
2 2 01 10 11 00 12 13
2 3 000 101 101 110 12 12 34
Sample Run:
Enter file name: values.txt
Set 1: (B OR (A AND B))
Set 2: (A XNOR (A XOR B))
Set 3: ((A OR B) XOR (A AND B))
Name the program: BoolExpressXX.cpp or BoolExpressXX.java, where XX are your initials.
6
See Attachments below:
• 2425PS2S22-1.pdf (Updated 2/27)
Data Files-PS 2
• PS 2 Files-1.zip
Samples with Text files- Java and C++
.
TextFileExamples-2.zip
