http://www.categories.acsl.org/wiki/api.php?action=feedcontributions&user=Jan&feedformat=atomACSL Category Descriptions - User contributions [en]2024-03-28T22:34:56ZUser contributionsMediaWiki 1.37.1http://www.categories.acsl.org/wiki/index.php?title=What_Does_This_Program_Do%3F&diff=841What Does This Program Do?2020-10-22T22:12:10Z<p>Jan: </p>
<hr />
<div>Frequently, one must use or modify sections of another programmer’s code. Since the original author is often unavailable to explain his/her code, and documentation is, unfortunately,<br />
not always available or sufficient, it is essential to be able to read and understand an arbitrary program. <br />
<br />
This category presents a program and asks the student to determine that the program does. The programs are written using a pseudocode that<br />
should be readily understandable by all programmers familiar with a high-level programming language, such as Python, Java, or C.<br />
<br />
= Description of the ACSL Pseudo-code =<br />
<br />
We will use the following constructs in writing this code for this topic in ACSL:<br />
<br />
{| class="wikitable" style="text-align: left"<br />
|-<br />
!'''Construct'''<br />
!'''Code Segment'''<br />
|-<br />
|Operators<br />
|! (not) , ^ or ↑(exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), <math>||</math> (or) in that order of precedence<br />
|-<br />
|Functions<br />
|abs(x) - absolute value, sqrt(x) - square root, int(x) - greatest integer <= x<br />
|-<br />
|Variables<br />
|Start with a letter, only letters and digits<br />
|-<br />
|Sequential statements<br />
|<br />
{| class="wikitable" style="text-align: left"<br />
|-<br />
|INPUT variable<br />
|-<br />
|variable = expression (assignment)<br />
|-<br />
|OUTPUT variable<br />
|}<br />
|-<br />
|Decision statements<br />
|<br />
{| class="wikitable" style="text-align: left"<br />
|-<br />
|IF boolean expression THEN<br />
|-<br />
|Statement(s)<br />
|-<br />
|ELSE (optional)<br />
|-<br />
|Statement(s)<br />
|-<br />
|END IF<br />
|}<br />
|-<br />
|Indefinite Loop statements<br />
|<br />
{| class="wikitable" style="text-align: left"<br />
|-<br />
|WHILE Boolean expression<br />
|-<br />
| Statement(s)<br />
|-<br />
|END WHILE<br />
|}<br />
|-<br />
|Definite Loop statements<br />
|<br />
{| class="wikitable" style="text-align: left"<br />
|-<br />
|FOR variable = start TO end STEP increment<br />
|-<br />
| Statement(s)<br />
|-<br />
|NEXT<br />
|}<br />
|-<br />
|Arrays:<br />
|1 dimensional arrays use a single subscript such as A(5). 2 dimensional arrays use (row, col) order such as A(2,3). Arrays can start at location 0 for 1 dimensional arrays and location (0,0) for 2 dimensional arrays. Most ACSL past problems start with either A(1) or A(1,1). The size of the array will usually be specified in the problem statement.<br />
|-<br />
|Strings:<br />
|Strings can contain 0 or more characters and the indexed position starts with 0 at the first character. An empty string has a length of 0. Errors occur if accessing a character that is in a negative position or equal to the length of the string or larger. The len(A) function will find the length of the string which is the total number of characters. Strings are identified with surrounding double quotes. Use [ ] for identifying the characters in a substring of a given string as follows: <br />
S = “ACSL WDTPD” (S has a length of 10 and D is at location 9)<br />
<br />
S[:3] = “ACS” (take the first 3 characters starting on the left) <br />
<br />
S[4:] = “DTPD” (take the last 4 characters starting on the right) <br />
<br />
S[2:6] = “SL WD” (take the characters starting at location 2 and ending at location 6)<br />
<br />
S[0] = “A” (position 0 only). <br />
<br />
String concatenation is accomplished using the + symbol<br />
|}<br />
<br />
The questions in this topic will cover any of the above constructs in the Intermediate and Senior Division. In the Junior Division, loops will not be included in contest 1; loops will be used in contest 2; strings will be used in contest 3; and arrays will be included in contest 4.<br />
<br />
= Sample Problems =<br />
<br />
== Problem 1 ==<br />
<br />
After this program is executed, what is the value of B that is printed if the input values are 50 and 10?<br />
<syntaxhighlight lang="text"><br />
input H, R<br />
B = 0<br />
if H>48 then<br />
B = B + (H - 48) * 2 * R<br />
H = 48<br />
end if<br />
if H>40 then<br />
B = B + (H - 40) * (3/2) * R<br />
H = 40<br />
end if<br />
B = B + H * R<br />
output B<br />
</syntaxhighlight><br />
'''Solution:'''<br />
<br />
This program computes an employee’s weekly salary, given the hourly rate (R) and the number of hours worked in the week (H). The employee is paid an hourly rate for the number of hours worked, up to 40, time and a half for the overtime hours, up to 48 hours, and double for all hours over 48. The table monitors variables B and H:<br />
{| class="wikitable"<br />
|-<br />
! | B || H<br />
|-<br />
| | 0 || 50<br />
|-<br />
| | 40 || 48<br />
|-<br />
| | 160 || 40<br />
|-<br />
| | 560 || 40<br />
|}<br />
<br />
Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.<br />
<br />
== Problem 2 ==<br />
<br />
After the following program is executed, what is the final value of NUM?<br />
<syntaxhighlight lang="text"><br />
A = “BANANAS”<br />
NUM = 0: T = “”<br />
for J = len(A) - 1 to 0 step –1<br />
T = T + A[j]<br />
next <br />
for J = 0 to len(A) - 1<br />
if A[J] == T[J] then NUM = NUM + 1<br />
next<br />
</syntaxhighlight><br />
<br />
'''Solution:'''<br />
<br />
The program first stores the reverse of variable A into variable T and then counts the number of letters that are in the same position in both strings.<br />
Variable NUM is incremented each time a character at position x of A is the same as the character in position x of string T. There are 5 such positions: 1, 2, 3, 4, and 5.<br />
<br />
== Problem 3 ==<br />
<br />
After the following program is executed, what is the final value of C[4]?<br />
<syntaxhighlight lang="text"><br />
A(0) = 12: A(1) = 41: A(2) = 52<br />
A(3) = 57: A(4) = 77: A(5) = -100<br />
B(0) = 17: B(1) = 34: B(20 = 81<br />
J = 0: K = 0: N = 0<br />
while A(J) > 0<br />
while B(K) <= A(J)<br />
C(N) = B(K)<br />
N = N + 1<br />
k = k + 1<br />
end while<br />
C(N) = A(J): N = N + 1: J = J + 1<br />
end while<br />
C(N) = B(K)<br />
</syntaxhighlight><br />
<br />
'''Solution:'''<br />
<br />
The following table traces the variables through the execution of the program. <br />
<br />
{| class="wikitable" <br />
|-<br />
!J<br />
!K<br />
!N<br />
!A(J)<br />
!B(K)<br />
!C(N)<br />
|-<br />
|0 || 0 || 0 || 12 || 17 || 12<br />
|-<br />
|1 || 0 || 1 || 41 || 17 || 17<br />
|-<br />
|1 || 1 || 2 || 41 || 34 || 34<br />
|-<br />
|1 || 2 || 3 || 41 || 81 || 41<br />
|-<br />
|2 || 2 || 4 || 52 || 81 || 52<br />
|-<br />
|3 || 2 || 5 || 57 || 81 || 57<br />
|-<br />
|4 || 2 || 6 || 77 || 81 || 77<br />
|-<br />
|5 || 2 || 7 || -100 || 81 || 81<br />
|}<br />
<br />
Thus, the value of C(4) is 52. Note that this program merges two arrays in increasing order into one array until a negative number is input.<br />
<br />
= Video Resources =<br />
<br />
The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.<br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/IBlXLEWeHjc</youtube><br />
| [https://youtu.be/IBlXLEWeHjc ''ACSL Math: What Does This Program Do?'' ('''Raj Joshi''')]<br />
<br />
This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.<br />
|}</div>Janhttp://www.categories.acsl.org/wiki/index.php?title=Bit-String_Flicking&diff=717Bit-String Flicking2020-08-25T01:50:50Z<p>Jan: /* Problem 1 */</p>
<hr />
<div><br />
Bit strings (strings of binary digits) are frequently manipulated bit-by-bit using the logical operators '''NOT''', '''AND''', '''OR''', and '''XOR'''. Bits strings are manipulated as a unit using '''SHIFT''' and '''CIRCULATE''' operators. The bits on the left are called the ''most significant bits'' and those on the right are the ''least significant bits''.<br />
<br />
Most high-level languages (e.g., Python, Java, C++), support bit-string operations. Programmers typically use bit strings to maintain a set of flags. Suppose that a program supports 8 options, each of which can be either “on” or “off”. One could maintain this information using an array of size 8, or one could use a single variable (if it is internally stored using at least 8 bits or 1 byte, which is usually the case) and represent each option with a single bit. In addition to saving space, the program is often cleaner if a single variable is involved rather than an array. Bits strings are often used to maintain a set where values are either in the set or not. Shifting of bits is also used to multiply or divide by powers of 2.<br />
<br />
Mastering this topic is essential for systems programming, programming in assembly language, optimizing code, and hardware design.<br />
<br />
== Operators==<br />
<br />
=== Bitwise Operators ===<br />
<br />
The logical operators are '''NOT''' (~ or $\neg$), '''AND''' (&), '''OR''' (|), and '''XOR''' ($\oplus$). These operators should be familiar to ACSL students from the [[Boolean Algebra]] and [[Digital Electronics]] categories.<br />
<br />
* '''NOT''' is a unary operator that performs logical negation on each bit. Bits that are 0 become 1, and those that are 1 become 0. For example: ~101110 has a value of 010001.<br />
<br />
* '''AND''' is a binary operator that performs the logical '''AND''' of each bit in each of its operands. The '''AND''' of two values is 1 only if both values are 1. For example, '''1011011 and 011001''' has a value of '''001001'''. The '''AND''' function is often used to isolate the value of a bit in a bit-string or to clear the value of a bit in a bit-string.<br />
<br />
* '''OR''' is a binary operator that performs the logical '''OR''' of each bit in each of its operands. The '''OR''' of two values is 1 only if one or both values are 1. For example, '''1011011 or 011001''' has a value of '''111011'''. The '''OR''' function is often use to force the value of a bit in a bit-string to be 1, if it isn't already.<br />
<br />
* '''XOR''' is a binary operator that performs the logical '''XOR''' of each bit in each of its operands. The '''XOR''' of two values is 1 if the values are different and 0 if they are the same. For example, '''1011011 xor 011001 = 110010'''. The '''XOR''' function is often used to change the value of a particular bit.<br />
<br />
All binary operators (AND, OR, or XOR) must operate on bit-strings that are of the same length. If the operands are not the same length, the shorter one is padded with 0's on the left as needed. For example, '''11010 and 1110''' would have value of '''11010 and 01110 = 01010'''.<br />
<br />
The following table summarizes the operators:<br />
<br />
::{| class="wikitable" style="text-align: center"<br />
|-<br />
!<math>x</math><br />
!<math>y</math><br />
! '''not''' <math>x</math><br />
!<math>x</math> '''and''' <math>y</math><br />
!<math>x</math> '''or''' <math>y</math><br />
!<math>x</math> '''xor''' <math>y</math><br />
|-<br />
!0<br />
!0<br />
| 1 <br />
| 0 <br />
| 0 <br />
| 0 <br />
|-<br />
!0<br />
!1<br />
| 1 <br />
| 0 <br />
| 1 <br />
| 1 <br />
|-<br />
!1<br />
!0<br />
| 0 <br />
| 0 <br />
| 1 <br />
| 1 <br />
|-<br />
!1<br />
!1<br />
| 0 <br />
| 1 <br />
| 1 <br />
| 0<br />
|}<br />
<br />
=== Shift Operators ===<br />
<br />
Logical shifts (LSHIFT-x and RSHIFT-x) “ripple” the bit-string x positions in the indicated direction, either to the left or to the right. Bits shifted out are lost; zeros are shifted in at the other end. <br />
<br />
Circulates (RCIRC-x and LCIRC-x) “ripple” the bit string x positions in the indicated direction. As each bit is shifted out one end, it is shifted in at the other end. The effect of this is that the bits remain in the same order on the other side of the string.<br />
<br />
The size of a bit-string does not change with shifts, or circulates. If any bit strings are initially of different lengths, all shorter ones are padded with zeros in the left bits until all strings are of the same length. <br />
<br />
The following table gives some examples of these operations:<br />
<br />
::{| class="wikitable" style="text-align: right"<br />
|-<br />
!x<br />
!(LSHIFT-2 x)<br />
!(RSHIFT-3 x)<br />
!(LCIRC-3 x)<br />
!(RCIRC-1 x)<br />
|-<br />
!01101<br />
| 10100<br />
| 00001<br />
| 01011<br />
| 10110<br />
|-<br />
!10<br />
| 00<br />
| 00<br />
| 01<br />
| 01<br />
|-<br />
!1110<br />
| 1000<br />
| 0001<br />
| 0111<br />
| 0111<br />
|-<br />
!1011011<br />
| 1101100<br />
| 0001011<br />
| 1011101<br />
| 1101101<br />
|}<br />
<br />
=== Order of Precedence ===<br />
<br />
The order of precedence (from highest to lowest) is: NOT; SHIFT and CIRC; AND; XOR; and finally, OR. In other words, all unary operators are performed on a single operator first. Operators with equal precedence are evaluated left to right; all unary operators bind from right to left.<br />
<br />
== Sample Problems ==<br />
<br />
=== Problem 1 ===<br />
<br />
Evaluate the following expression: <br />
:(101110 AND NOT 110110 OR (LSHIFT-3 101010))<br />
<br />
'''Solution:'''<br />
The expression evaluates as follows:<br />
:(101110 AND '''001001''' OR (LSHIFT-3 101010))<br />
:('''001000''' OR (LSHIFT-3 101010))<br />
:(001000 OR '''010000''')<br />
:'''011000'''<br />
<br />
=== Problem 2 ===<br />
<br />
Evaluate the following expression: <br />
:(RSHIFT-1 (LCIRC-4 (RCIRC-2 01101))) <br />
<br />
'''Solution:'''<br />
The expression evaluates as follows, starting at the innermost parentheses:<br />
:(RCIRC-2 01101) => 01011<br />
:(LCIRC-4 01011) => 10101<br />
:(RSHIFT-1 10101) = 01010<br />
<br />
=== Problem 3 ===<br />
<br />
List all possible values of x (5 bits long) that solve the following equation.<br />
:(LSHIFT-1 (10110 XOR (RCIRC-3 x) AND 11011)) = 01100<br />
<br />
'''Solution:'''<br />
Since x is a string 5 bits long, represent it by abcde.<br />
:(RCIRC-3 abcde) => cdeab<br />
:(cdeab AND 11011) => cd0ab<br />
:(10110 XOR cd0ab) => Cd1Ab (the capital letter is the NOT of its lower case)<br />
:(LSHIFT-1 Cd1Ab) => d1Ab0<br />
<br />
So, d1Ab0 = 01100.<br />
<br />
Meaning, we must have d=0, A=1 (hence a=0), b=0. Thus, the solution must be in the form 00*0*, where * is an “I-don’t-care”. <br />
<br />
The four possible values of x are: 00000, 00001, 00100 and 00101.<br />
<br />
=== Problem 4 ===<br />
<br />
Evaluate the following expression:<br />
: ((RCIRC-14 (LCIRC-23 01101)) | (LSHIFT-1 10011) & (RSHIFT-2 10111))<br />
<br />
'''Solution:'''<br />
The problem can be rewritten as <br />
: A | B & C<br />
The AND has higher precedence than the OR. <br />
<br />
The evaluation of expression A can be done in a straightforward way: (LCIRC-23 01101) is the same as (LCIRC-3 01101) which has a value of 01011, and (RCIRC-14 01011) is the same as (RCIRC-4 01011) which has a value of 10110. Another strategy is to offset the left and right circulates. So, ((RCIRC-14 (LCIRC-23 01101)) has the same value as (LCIRC-9 01101), which has the same value as (LCIRC-4 01101) which is also 11010.<br />
<br />
Expressions B and C are pretty easy to evaluate:<br />
:B = (LSHIFT-1 10011) = 00110<br />
:C = (RSHIFT-2 10111) = 00101<br />
<br />
The expression becomes<br />
: A | B & C = 10110 | 00110 & 00101 = 10110 | 00100 = 10110<br />
<br />
== Video Resources ==<br />
<br />
The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads. <br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/0U6ogoQ5Hkk</youtube><br />
| [https://youtu.be/0U6ogoQ5Hkk "ACSL Math: Bit String Flicking" (Quick Coding Bytes)]<br />
<br />
This video introduces the topic, then using an example problem, explains the methodology to solve problems that appear on ACSL contests.<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/IeMsD3harrE</youtube><br />
| [https://youtu.be/IeMsD3harrE ''Bit String Flicking (Intro)'' ('''CalculusNguyenify''')]<br />
<br />
A great two-part tutorial on this ACSL category. Part 1 covers bitwise operations AND, OR, NOT, and XOR. <br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/jbKw8oYJPs4</youtube><br />
| [https://youtu.be/jbKw8oYJPs4 ''Bit String Flicking Shifts and Circs'' ('''CalculusNguyenify''')]<br />
<br />
Part 2 covers logical shifts and circulate operations.<br />
<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/XNBcO25mgCw</youtube><br />
| [https://youtu.be/XNBcO25mgCw ''Bit String Flicking'' ('''Tangerine Code''')]<br />
<br />
Shows the solution to the problem: (RSHIFT-3 (LCIRC-2 (NOT 10110)))<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/8J9AdxU5CW8</youtube><br />
| [https://youtu.be/8J9AdxU5CW8 ''Bit String Flicking by Ravi Yeluru'' ('''hemsra''')]<br />
<br />
Walks through two problems from the Junior Division.<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/aa_lQ8gft60</youtube><br />
| [https://youtu.be/aa_lQ8gft60 ''ACSL BitString Flicking Contest 2 Worksheet 1'' ('''misterminich''')]<br />
<br />
Solves a handful of problems given in previous years at the Intermediate Division level.<br />
<br />
|}<br />
<br />
<br />
<br />
<!--<br />
{|<br />
|-<br />
| <youtube width="300" height="180">URL</youtube><br />
| [URL ''TITLE'' ('''AUTHOR''')]<br />
<br />
DESCRIPTION<br />
|}<br />
--></div>Janhttp://www.categories.acsl.org/wiki/index.php?title=FSAs_and_Regular_Expressions&diff=716FSAs and Regular Expressions2020-08-21T01:51:41Z<p>Jan: /* More useful patterns */</p>
<hr />
<div>A Finite State Automaton (FSA) is a mathematical model of computation comprising all 4 of the following: 1) a finite number of ''states'', of which exactly one is ''active'' at any given time; 2) ''transition rules'' to change the active state; 3) an ''initial state''; and 4) one or more ''final states''. We can draw an FSA by representing each state as a circle, the final state as a double circle, the start state as the only state with an incoming arrow, and the transition rules as labeled-edges connecting the states. When labels are assigned to states, they appear inside the circle representing the state. <br />
<br />
In this category, FSAs will be limited to parsing strings. That is, determining if a string is valid or not. <br />
<br />
= Basics =<br />
<br />
Here is a drawing of an FSA that is used to parse strings consisting of x's and y's:<br />
<br />
<center><br />
[[File:fsa.svg|250px]]<br />
</center><br />
<br />
In the above FSA, there are three states: A, B, and C. The initial state is A; the final state is C. The only way to go from state A to B is by ''seeing'' the letter x. Once in state B, there are two transition rules: seeing the letter y will cause the FSA to make C the active state, and seeing an x will keep B as the active state. State C is a final state so if the string being parsed is completed and the FSA is in State C, the input string is said to be ''accepted'' by the FSA. In State C, seeing any additional letter y will keep the machine in state C. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy, xxyyyy). <br />
<br />
A Regular Expression (RE) is an algebraic representation of an FSA. For example, the regular expression corresponding to the first FSA given above is xx*yy*. <br />
<br />
The rules for forming a Regular Expression (RE) are as follows:<br />
:1. The null string (λ) is a RE.<br />
:2. If the string a is in the input alphabet, then it is a RE.<br />
:3. if a and b are both REs, then so are the strings built up using the following rules:<br />
::a. CONCATENATION. "ab" (a followed by b).<br />
::b. UNION. "aUb" or "a|b" (a or b). <br />
::c. CLOSURE. "a*" (a repeated zero or more times). This is known as the Kleene Star.<br />
<br />
The order of precedence for Regular Expression operators is: Kleene Star, concatenation, and then union. <br />
Similar to standard Algebra, parentheses can be used to group sub-expressions. <br />
For example, "dca*b" generates strings dcb, dcab, dcaab, and so on, whereas<br />
"d(ca)*b" generates strings db, dcab, dcacab, dcacacab, and so on.<br />
<br />
If we have a Regular Expression, then we can mechanically build an FSA to accept the strings which are generated by the Regular Expression. Conversely, if we have an FSA, we can mechanically develop a Regular Expression which will describe the strings which can be parsed by the FSA. For a given FSA or Regular Expression, there are many others which are equivalent to it. A "most simplified" Regular Expression or FSA is not always well defined.<br />
<br />
= Regular Expression Identities =<br />
<br />
{| Class="wikitable"<br />
|-<br />
|1. (a*)* = a*<br />
|-<br />
|2. aa* = a*a<br />
|-<br />
|3. aa* U λ = a*<br />
|-<br />
|4. a(b U c) = ab U ac<br />
|-<br />
|5. a(ba)* = (ab)*a<br />
|-<br />
|6. (a U b)* = (a* U b*)*<br />
|-<br />
|7. (a U b)* = (a*b*)*<br />
|-<br />
|8. (a U b)* = a*(ba*)*<br />
|}<br />
<br />
= RegEx in Practice =<br />
<br />
Programmers use Regular Expressions (usually referred to as '''regex''') extensively for<br />
expressing patterns to search for. All modern programming languages have regular expression libraries.<br />
<br />
Unfortunately, the specific syntax rules vary depending on the specific <br />
implementation, programming language, or library in use. <br />
Interactive websites for testing regexes are a useful resource for <br />
learning regexes by experimentation. <br />
An excellent online tool is [https://regex101.com/ https://regex101.com/]. <br />
A very nice exposition is [https://automatetheboringstuff.com/2e/chapter7/ Pattern Matching with Regular Expressions] <br />
from the [https://automatetheboringstuff.com/ Automate the Boring Stuff] book and online course.<br />
<br />
Here are the additional syntax rules that we will use. They are pretty universal across all<br />
regex packages. <br />
<br />
{| class="wikitable" style="text-align: left"|<br />
|-<br />
!Pattern<br />
!Description<br />
|-<br />
! <nowiki>|</nowiki><br />
|As described above, a vertical bar separates alternatives. For example, gray<nowiki>|</nowiki>grey can match "gray" or "grey".<br />
|-<br />
!*<br />
|As described above, the asterisk indicates zero or more occurrences of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.<br />
|-<br />
!?<br />
| The question mark indicates zero or one occurrences of the preceding element. For example, colou?r matches both "color" and "colour".<br />
|-<br />
! +<br />
| The plus sign indicates one or more occurrences of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".<br />
|-<br />
! .<br />
| The wildcard . matches any character. For example, a.b matches any string that contains an "a", then any other character, and then a "b" such as "a7b", "a&b", or "arb", but not "abbb". Therefore, a.*b matches any string that contains an "a" and a "b" with 0 or more characters in between. This includes "ab", "acb", or "a123456789b".<br />
|-<br />
! [ ]<br />
| A bracket expression matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z].<br />
|-<br />
! [^ ]<br />
|Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed.<br />
|-<br />
!( )<br />
| <br />
As described above, parentheses define a sub-expression. For example, the pattern H(ä|ae?)ndel matches "Handel", "Händel", and "Haendel".<br />
|}<br />
<br />
== More useful patterns ==<br />
{| class="wikitable" style="text-align: left"|<br />
|-<br />
! Pattern !! Description !! REGEX !! Sample match !! Sample<br />
not match <br />
|-<br />
| \d || '''Digit.'''<br />
Matches any digit. Equivalent with [0-9].<br />
|| \d\d\d || 123 || 1-3<br />
|-<br />
| \D || '''Non digit.'''<br />
Matches any character that is not a digit.<br />
|| \d\D\d || 1-3 || 123<br />
|-<br />
| \w || '''Word.''' <br />
Matches any alphanumeric character and underscore. Equivalent with [a-zA-Z0-9_].<br />
|| \w\w\w || a_A || a-A<br />
|-<br />
| \W || '''Not Word.'''<br />
Matches any character that is not word character (alphanumeric character and underscore).<br />
|| \W\W\W || +-$ || +_@<br />
|-<br />
| \s || '''Whitespace.'''<br />
Matches any whitespace character (space, tab, line breaks).<br />
|| \d\s\w || 1 a || 1ab<br />
|-<br />
| \S || '''Not Whitespace.'''<br />
Matches any character that is not a whitespace character (space, tab, line breaks). <br />
|| \w\w\w\w\S\d || Test#1 || test 1<br />
|-<br />
| \b || '''Word boundaries.'''<br />
Can be used to match a complete word. Word boundaries are the boundaries between a word<br />
<br />
and a non-word character.<br />
|| \bis\b || is; || This <br />
island:<br />
|-<br />
|{} || '''The curly braces {…}.'''<br />
<br />
It tells the computer to repeat the preceding character (or set of characters) for<br />
<br />
as many times as the value inside this bracket.<br />
<br />
'''{min,}''' means the preceding character is matches '''min''' times or '''more'''. <br />
<br />
'''{min,max}''' means that the preceding character is repeated at least '''min''' and<br />
at most '''max''' times.<br />
||<br />
abc{2}<br />
|| <br />
abcc<br />
|| <br />
abc<br />
|-<br />
|''' .*''' || Matches any character (except for line terminators), matches between zero and unlimited times.<br />
<br />
|| .*<br />
||<br />
abbb<br />
<br />
Empty string<br />
<br />
|| <br />
|-<br />
|''' .+''' || Matches any character (except for line terminators), matches between one and unlimited times.<br />
|| .+<br />
|| a<br />
abbcc<br />
<br />
|| Empty string<br />
|-<br />
| ^ || '''Anchor ^.The start of the line.'''<br />
Matches position just before the first character of the string.<br />
||^The\s\w+ || The contest || One contest<br />
|-<br />
| $ || '''Anchor $. The end of the line.'''<br />
Matches position just after the last character of the string.<br />
||\d{4}\sACSL$<br />
||2020 ACSL<br />
||2020 STAR<br />
|-<br />
| \||'''Escape a special character.'''<br />
If you want to use any of the metacharacters as a literal in a regex, you need to escape them with a backslash,<br />
like: \. \* \+ \[ etc.<br />
||\w\w\w'''\.''' ||cat'''.''' ||lion<br />
|-<br />
| ()|| '''Groups.'''<br />
Regular expressions allow us to not just match text but also to '''extract information<br />
for further processing.<br />
This is done by defining '''groups of characthers''' and capturing them using <br />
the parentheses '''()'''.<br />
<br />
|| ^(file.+)\.docx$ || file_graphs.docx<br />
file_lisp.docx <br />
|| data.docx<br />
|-<br />
| \number || '''Backreference.'''<br />
A set of different symbols of a regular expression can be grouped together to act as a single unit and behave as a block.<br />
<br />
'''\n''' means that the group enclosed within the '''n-th''' bracket will be repeated at current position.<br />
|| || ||<br />
|-<br />
| \1 || '''Contents of Group 1.''' || r(\w)g'''\1'''x || regex<br />
Group '''\1''' is e<br />
|| regxx<br />
|-<br />
| \2 ||'''Contents of Group 2.''' || (\d\d)\+(\d\d)='''\2'''\+'''\1''' || 20+21=21+20<br />
Group '''\1''' is 20<br />
<br />
Group '''\2''' is 21<br />
|| 20+21=20+21<br />
|}<br />
<br />
= Sample Problems =<br />
<br />
Typical problems in the category will include: translate an FSA to a Regular Expression; simplify a Regular Expression; determine which Regular Expressions or FSAs are equivalent; and determine which strings are accepted by either an FSA or a Regular Expression.<br />
<br />
== Problem 1 ==<br />
<br />
Find a simplified Regular Expression for the following FSA:<br />
<br />
[[File:fsa_s1.png]]<br />
<br />
'''Solution:'''<br />
<br />
The expression 01*01 is read directly from the FSA. It is in its most simplified form.<br />
<br />
== Problem 2 ==<br />
<br />
Which of the following strings are accepted by the following Regular Expression "00*1*1U11*0*0" ?<br />
<br />
::A. 0000001111111<br />
::B. 1010101010<br />
::C. 1111111<br />
::D. 0110<br />
::E. 10 <br />
<br />
'''Solution:'''<br />
<br />
This Regular Expression parses strings described by the union of 00*1*1 and 11*0*0. The RE 00*1*1 matches strings starting with one or more 0s followed by one or more 1s: 01, 001, 0001111, and so on. The RE 11*0*0 matches strings with one or more 1s followed by one or more 0s: 10, 1110, 1111100, and so on. In other words, strings of the form: 0s followed by some 1s; or 1s followed by some 0s. Choice A and E following this pattern.<br />
<br />
<!--<br />
== Problem 3 ==<br />
<br />
Which, if any, of the following Regular Expressions are equivalent?<br />
::A. (a U b)(ab*)(b* U a)<br />
::B. (aab* U bab*)a<br />
::C. aab* U bab* U aaba U bab*a<br />
::D. aab* U bab* U aab*a U bab*a<br />
::E. a* U b* <br />
<br />
'''Solution:'''<br />
<br />
Choice B can be discarded because it is the only RE whose strings '''must''' end with an a. Choice E can be discarded since it is the only RE that can accept a null string. Choices C and D are not equal. After expanding choice A, we must compare it to choices C and D. It is equal to choice D, but not to choice C. The only REs that are equivalent are choices A and D.<br />
--><br />
== Problem 3 ==<br />
<br />
Which of the following strings match the regular expression pattern "[A-D]*[a-d]*[0-9]" ?<br />
<br />
::1. ABCD8<br />
::2. abcd5<br />
::3. ABcd9<br />
::4. AbCd7<br />
::5. X<br />
::6. abCD7<br />
::7. DCCBBBaaaa5<br />
<br />
'''Solution:'''<br />
<br />
The pattern describes strings the start with zero or more uppercase letters A, B, C, or D (in any order), followed<br />
by zero or more lowercase letter a, b, c, or d (in any order), followed by a single digit.<br />
The strings that are represented by this pattern are 1, 2, 3, and 7.<br />
<br />
== Problem 4 ==<br />
<br />
Which of the following strings match the regular expression pattern "Hi?g+h+[^a-ceiou]" ?<br />
<br />
::1. Highb<br />
::2. HiiighS<br />
::3. HigghhhC<br />
::4. Hih<br />
::5. Hghe<br />
::6. Highd<br />
::7. HgggggghX<br />
<br />
'''Solution:'''<br />
<br />
The ? indicates 0 or 1 "i"s. The + indicates 1 or more "g"s followed by 1 or more "h"s. <br />
The ^ indicates that the last character cannot be lower-case a, b, c, e, i, o, or u.<br />
The strings that are represented by this pattern are 3, 6, and 7. <br />
<br />
<!--<br />
== Problem 5 ==<br />
<br />
Which of the following strings match the regular expression pattern "[A-E|a-e]*(00[01])|([10]11)" ?<br />
<br />
::1. DAD001<br />
::2. bad000<br />
::3. aCe0011<br />
::4. AbE111<br />
::5. AAAbbC<br />
::6. aBBBe011<br />
::7. 001011<br />
<br />
'''Solution:'''<br />
<br />
The [A-E|a-e]* allows for any of those letters in any order 0 or more times. Therefore, all of the <br />
choices match at the beginning of the string. The end of the string must match "000", "001", "111", <br />
or "011". That means that 1, 2, 4, and 6 match.<br />
--><br />
== Problem 5 ==<br />
<br />
Which of the following strings match the regular expression pattern "^w{3}\.([a-z0-9]([-a-z0-9]{0,61}[a-z0-9])+\.)+[a-z0-9][-a-z0-9]{0,61}[a-z0-9]" ?<br />
<br />
::1. www.google.com<br />
::2. www.-petsmart.com<br />
::3. www.edu-.ro<br />
::4. www.google.co.in<br />
::5. www.examples.c.net<br />
::6. www.edu.training.computer-science.org<br />
::7. www.everglades_holidaypark.com<br />
<br />
'''Solution:'''<br />
This Regular Expression matches a domain name used to access web sites.<br />
<br />
RE starts with the subdomain www, continues with a number of names of domains, separated by a dot (Top-level domain (TLD), Second-level domain (SLD), Third-level domain, and so on).<br />
<br />
The name of a domain contains only small letters, digits and hyphen. The name can’t begin and can’t finish with a hyphen character. The length of the domain’s name is minimum 2 and maximum 63 characters.<br />
<br />
'''^''': the string starts with '''www''', followed by a dot character;<br />
<br />
'''[a-z0-9]''' : the first and the last character of the domain's name can be only a small letter or a digit;<br />
<br />
'''[-a-z0-9]{0,61}''': the next characters can be small letters, digits or a hyphen character. Maximum 61 characters;<br />
<br />
The last sequence '''[a-z0-9][-a-z0-9]{0,61}[a-z0-9]''' is for the Top-Level domain, which is not followed by a dot.<br />
<br />
The strings that are represented by this pattern are 1, 4 and 6.<br />
<br />
= Video Resources =<br />
<br />
Nice two-part video showing the relationship between FSAs and REs. <br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/GwsU2LPs85U</youtube><br />
| [https://youtu.be/GwsU2LPs85U ''1 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/shN_kHBFOUE</youtube><br />
| [https://youtu.be/shN_kHBFOUE ''2 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]<br />
<br />
This video uses the symbol "+" to mean "1 or more matches of the previous term". For example, "ab+" is the same as "abb*". In terms of the Kleene Star, zz* = z*z = z+.<br />
|}<br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/vI_yv0WuAhk</youtube><br />
| [https://youtu.be/vI_yv0WuAhk ''ACSL Test Prep - Finite State Automaton & Regular Expressions Explained'' ('''Mrs. Gupta''')]<br />
<br />
A talked-over presentation discussing the finite state automatons and regular expressions as needed for the American Computer Science League and its tests. <br />
|}<br />
<br />
<!--<br />
{|<br />
|-<br />
| <youtube width="300" height="180">URL</youtube><br />
| [URL ''TITLE'' ('''AUTHOR''')]<br />
<br />
DESCRIPTION<br />
|}<br />
--></div>Janhttp://www.categories.acsl.org/wiki/index.php?title=FSAs_and_Regular_Expressions&diff=715FSAs and Regular Expressions2020-08-21T01:51:37Z<p>Jan: /* More useful patterns */</p>
<hr />
<div>A Finite State Automaton (FSA) is a mathematical model of computation comprising all 4 of the following: 1) a finite number of ''states'', of which exactly one is ''active'' at any given time; 2) ''transition rules'' to change the active state; 3) an ''initial state''; and 4) one or more ''final states''. We can draw an FSA by representing each state as a circle, the final state as a double circle, the start state as the only state with an incoming arrow, and the transition rules as labeled-edges connecting the states. When labels are assigned to states, they appear inside the circle representing the state. <br />
<br />
In this category, FSAs will be limited to parsing strings. That is, determining if a string is valid or not. <br />
<br />
= Basics =<br />
<br />
Here is a drawing of an FSA that is used to parse strings consisting of x's and y's:<br />
<br />
<center><br />
[[File:fsa.svg|250px]]<br />
</center><br />
<br />
In the above FSA, there are three states: A, B, and C. The initial state is A; the final state is C. The only way to go from state A to B is by ''seeing'' the letter x. Once in state B, there are two transition rules: seeing the letter y will cause the FSA to make C the active state, and seeing an x will keep B as the active state. State C is a final state so if the string being parsed is completed and the FSA is in State C, the input string is said to be ''accepted'' by the FSA. In State C, seeing any additional letter y will keep the machine in state C. The FSA above will accept strings composed of one or more x’s followed by one or more y’s (e.g., xy, xxy, xxxyy, xyyy, xxyyyy). <br />
<br />
A Regular Expression (RE) is an algebraic representation of an FSA. For example, the regular expression corresponding to the first FSA given above is xx*yy*. <br />
<br />
The rules for forming a Regular Expression (RE) are as follows:<br />
:1. The null string (λ) is a RE.<br />
:2. If the string a is in the input alphabet, then it is a RE.<br />
:3. if a and b are both REs, then so are the strings built up using the following rules:<br />
::a. CONCATENATION. "ab" (a followed by b).<br />
::b. UNION. "aUb" or "a|b" (a or b). <br />
::c. CLOSURE. "a*" (a repeated zero or more times). This is known as the Kleene Star.<br />
<br />
The order of precedence for Regular Expression operators is: Kleene Star, concatenation, and then union. <br />
Similar to standard Algebra, parentheses can be used to group sub-expressions. <br />
For example, "dca*b" generates strings dcb, dcab, dcaab, and so on, whereas<br />
"d(ca)*b" generates strings db, dcab, dcacab, dcacacab, and so on.<br />
<br />
If we have a Regular Expression, then we can mechanically build an FSA to accept the strings which are generated by the Regular Expression. Conversely, if we have an FSA, we can mechanically develop a Regular Expression which will describe the strings which can be parsed by the FSA. For a given FSA or Regular Expression, there are many others which are equivalent to it. A "most simplified" Regular Expression or FSA is not always well defined.<br />
<br />
= Regular Expression Identities =<br />
<br />
{| Class="wikitable"<br />
|-<br />
|1. (a*)* = a*<br />
|-<br />
|2. aa* = a*a<br />
|-<br />
|3. aa* U λ = a*<br />
|-<br />
|4. a(b U c) = ab U ac<br />
|-<br />
|5. a(ba)* = (ab)*a<br />
|-<br />
|6. (a U b)* = (a* U b*)*<br />
|-<br />
|7. (a U b)* = (a*b*)*<br />
|-<br />
|8. (a U b)* = a*(ba*)*<br />
|}<br />
<br />
= RegEx in Practice =<br />
<br />
Programmers use Regular Expressions (usually referred to as '''regex''') extensively for<br />
expressing patterns to search for. All modern programming languages have regular expression libraries.<br />
<br />
Unfortunately, the specific syntax rules vary depending on the specific <br />
implementation, programming language, or library in use. <br />
Interactive websites for testing regexes are a useful resource for <br />
learning regexes by experimentation. <br />
An excellent online tool is [https://regex101.com/ https://regex101.com/]. <br />
A very nice exposition is [https://automatetheboringstuff.com/2e/chapter7/ Pattern Matching with Regular Expressions] <br />
from the [https://automatetheboringstuff.com/ Automate the Boring Stuff] book and online course.<br />
<br />
Here are the additional syntax rules that we will use. They are pretty universal across all<br />
regex packages. <br />
<br />
{| class="wikitable" style="text-align: left"|<br />
|-<br />
!Pattern<br />
!Description<br />
|-<br />
! <nowiki>|</nowiki><br />
|As described above, a vertical bar separates alternatives. For example, gray<nowiki>|</nowiki>grey can match "gray" or "grey".<br />
|-<br />
!*<br />
|As described above, the asterisk indicates zero or more occurrences of the preceding element. For example, ab*c matches "ac", "abc", "abbc", "abbbc", and so on.<br />
|-<br />
!?<br />
| The question mark indicates zero or one occurrences of the preceding element. For example, colou?r matches both "color" and "colour".<br />
|-<br />
! +<br />
| The plus sign indicates one or more occurrences of the preceding element. For example, ab+c matches "abc", "abbc", "abbbc", and so on, but not "ac".<br />
|-<br />
! .<br />
| The wildcard . matches any character. For example, a.b matches any string that contains an "a", then any other character, and then a "b" such as "a7b", "a&b", or "arb", but not "abbb". Therefore, a.*b matches any string that contains an "a" and a "b" with 0 or more characters in between. This includes "ab", "acb", or "a123456789b".<br />
|-<br />
! [ ]<br />
| A bracket expression matches a single character that is contained within the brackets. For example, [abc] matches "a", "b", or "c". [a-z] specifies a range which matches any lowercase letter from "a" to "z". These forms can be mixed: [abcx-z] matches "a", "b", "c", "x", "y", or "z", as does [a-cx-z].<br />
|-<br />
! [^ ]<br />
|Matches a single character that is not contained within the brackets. For example, [^abc] matches any character other than "a", "b", or "c". [^a-z] matches any single character that is not a lowercase letter from "a" to "z". Likewise, literal characters and ranges can be mixed.<br />
|-<br />
!( )<br />
| <br />
As described above, parentheses define a sub-expression. For example, the pattern H(ä|ae?)ndel matches "Handel", "Händel", and "Haendel".<br />
|}<br />
<br />
== More useful patterns ==<br />
{| class="wikitable" style="text-align: left"|<br />
|-<br />
! Pattern !! Description !! REGEX !! Sample match !! Sample<br />
not match <br />
|-<br />
| \d || '''Digit.'''<br />
Matches any digit. Equivalent with [0-9].<br />
|| \d\d\d || 123 || 1-3<br />
|-<br />
| \D || '''Non digit.'''<br />
Matches any character that is not a digit.<br />
|| \d\D\d || 1-3 || 123<br />
|-<br />
| \w || '''Word.''' <br />
Matches any alphanumeric character and underscore. Equivalent with [a-zA-Z0-9_].<br />
|| \w\w\w || a_A || a-A<br />
|-<br />
| \W || '''Not Word.'''<br />
Matches any character that is not word character (alphanumeric character and underscore).<br />
|| \W\W\W || +-$ || +_@<br />
|-<br />
| \s || '''Whitespace.'''<br />
Matches any whitespace character (space, tab, line breaks).<br />
|| \d\s\w || 1 a || 1ab<br />
|-<br />
| \S || '''Not Whitespace.'''<br />
Matches any character that is not a whitespace character (space, tab, line breaks). <br />
|| \w\w\w\w\S\d || Test#1 || test 1<br />
|-<br />
| \b || '''Word boundaries.'''<br />
Can be used to match a complete word. Word boundaries are the boundaries between a word<br />
<br />
and a non-word character.<br />
|| \bis\b || is; || This <br />
island:<br />
|-<br />
|{} || '''The curly braces {…}.'''<br />
<br />
It tells the computer to repeat the preceding character (or set of characters) for<br />
<br />
as many times as the value inside this bracket.<br />
<br />
'''{min,}''' means the preceding character is matches '''min''' times or '''more'''. <br />
<br />
'''{min,max}''' means that the preceding character is repeated at least '''min''' and<br />
at most '''max''' times.<br />
||<br />
abc{2}<br />
|| <br />
abcc<br />
|| <br />
abc<br />
|-<br />
|''' .*''' || Matches any character (except for line terminators), matches between zero and unlimited times.<br />
<br />
|| .*<br />
||<br />
abbb<br />
<br />
Empty string<br />
<br />
|| <br />
|-<br />
|''' .+''' || Matches any character (except for line terminators), matches between one and unlimited times.<br />
|| .+<br />
|| a<br />
abbcc<br />
<br />
|| Empty string<br />
|-<br />
| ^ || '''Anchor ^.The start of the line.'''<br />
Matches position just before the first character of the string.<br />
||^The\s\w+ || The contest || One contest<br />
|-<br />
| $ || '''Anchor $. The end of the line.'''<br />
Matches position just after the last character of the string.<br />
||\d{4}\sACSL$<br />
||2020 ACSL<br />
||2020 STAR<br />
|-<br />
| \||'''Escape a special character.'''<br />
If you want to use any of the metacharacters as a literal in a regex, you need to escape them with a backslash,<br />
like: \. \* \+ \[ etc.<br />
||\w\w\w'''\.''' ||cat'''.''' ||lion<br />
|-<br />
| ()|| '''Groups.'''<br />
Regular expressions allow us to not just match text but also to '''extract information<br />
for further processing.<br />
This is done by defining '''groups of characthers''' and capturing them using <br />
the parentheses '''()'''.<br />
<br />
|| ^(file.+)\.docx$ || file_graphs.docx<br />
file_lisp.docx <br />
|| data.docx<br />
|-<br />
| \number || '''Backreference.'''<br />
A set of different symbols of a regular expression can be grouped together to act as a single unit and behave as a block.<br />
<br />
'''\n''' means that the group enclosed within the '''n-th''' bracket will be repeated at current position.<br />
|| || ||<br />
|-<br />
| \1 || '''Contents of Group 1.''' || r(\w)g'''\1'''x || regex<br />
Group '''\1''' is e<br />
|| regxx<br />
|-<br />
| \2 ||'''Contents of Group 2.''' || (\d\d)\+(\d\d)='''\2'''\+'''\1''' || 20+21=21+20<br />
Group '''\1''' is 20<br />
<br />
Group '''\2''' is 21<br />
|| 20+21=20+21<br />
|}<br />
<br />
= Sample Problems =<br />
<br />
Typical problems in the category will include: translate an FSA to a Regular Expression; simplify a Regular Expression; determine which Regular Expressions or FSAs are equivalent; and determine which strings are accepted by either an FSA or a Regular Expression.<br />
<br />
== Problem 1 ==<br />
<br />
Find a simplified Regular Expression for the following FSA:<br />
<br />
[[File:fsa_s1.png]]<br />
<br />
'''Solution:'''<br />
<br />
The expression 01*01 is read directly from the FSA. It is in its most simplified form.<br />
<br />
== Problem 2 ==<br />
<br />
Which of the following strings are accepted by the following Regular Expression "00*1*1U11*0*0" ?<br />
<br />
::A. 0000001111111<br />
::B. 1010101010<br />
::C. 1111111<br />
::D. 0110<br />
::E. 10 <br />
<br />
'''Solution:'''<br />
<br />
This Regular Expression parses strings described by the union of 00*1*1 and 11*0*0. The RE 00*1*1 matches strings starting with one or more 0s followed by one or more 1s: 01, 001, 0001111, and so on. The RE 11*0*0 matches strings with one or more 1s followed by one or more 0s: 10, 1110, 1111100, and so on. In other words, strings of the form: 0s followed by some 1s; or 1s followed by some 0s. Choice A and E following this pattern.<br />
<br />
<!--<br />
== Problem 3 ==<br />
<br />
Which, if any, of the following Regular Expressions are equivalent?<br />
::A. (a U b)(ab*)(b* U a)<br />
::B. (aab* U bab*)a<br />
::C. aab* U bab* U aaba U bab*a<br />
::D. aab* U bab* U aab*a U bab*a<br />
::E. a* U b* <br />
<br />
'''Solution:'''<br />
<br />
Choice B can be discarded because it is the only RE whose strings '''must''' end with an a. Choice E can be discarded since it is the only RE that can accept a null string. Choices C and D are not equal. After expanding choice A, we must compare it to choices C and D. It is equal to choice D, but not to choice C. The only REs that are equivalent are choices A and D.<br />
--><br />
== Problem 3 ==<br />
<br />
Which of the following strings match the regular expression pattern "[A-D]*[a-d]*[0-9]" ?<br />
<br />
::1. ABCD8<br />
::2. abcd5<br />
::3. ABcd9<br />
::4. AbCd7<br />
::5. X<br />
::6. abCD7<br />
::7. DCCBBBaaaa5<br />
<br />
'''Solution:'''<br />
<br />
The pattern describes strings the start with zero or more uppercase letters A, B, C, or D (in any order), followed<br />
by zero or more lowercase letter a, b, c, or d (in any order), followed by a single digit.<br />
The strings that are represented by this pattern are 1, 2, 3, and 7.<br />
<br />
== Problem 4 ==<br />
<br />
Which of the following strings match the regular expression pattern "Hi?g+h+[^a-ceiou]" ?<br />
<br />
::1. Highb<br />
::2. HiiighS<br />
::3. HigghhhC<br />
::4. Hih<br />
::5. Hghe<br />
::6. Highd<br />
::7. HgggggghX<br />
<br />
'''Solution:'''<br />
<br />
The ? indicates 0 or 1 "i"s. The + indicates 1 or more "g"s followed by 1 or more "h"s. <br />
The ^ indicates that the last character cannot be lower-case a, b, c, e, i, o, or u.<br />
The strings that are represented by this pattern are 3, 6, and 7. <br />
<br />
<!--<br />
== Problem 5 ==<br />
<br />
Which of the following strings match the regular expression pattern "[A-E|a-e]*(00[01])|([10]11)" ?<br />
<br />
::1. DAD001<br />
::2. bad000<br />
::3. aCe0011<br />
::4. AbE111<br />
::5. AAAbbC<br />
::6. aBBBe011<br />
::7. 001011<br />
<br />
'''Solution:'''<br />
<br />
The [A-E|a-e]* allows for any of those letters in any order 0 or more times. Therefore, all of the <br />
choices match at the beginning of the string. The end of the string must match "000", "001", "111", <br />
or "011". That means that 1, 2, 4, and 6 match.<br />
--><br />
== Problem 5 ==<br />
<br />
Which of the following strings match the regular expression pattern "^w{3}\.([a-z0-9]([-a-z0-9]{0,61}[a-z0-9])+\.)+[a-z0-9][-a-z0-9]{0,61}[a-z0-9]" ?<br />
<br />
::1. www.google.com<br />
::2. www.-petsmart.com<br />
::3. www.edu-.ro<br />
::4. www.google.co.in<br />
::5. www.examples.c.net<br />
::6. www.edu.training.computer-science.org<br />
::7. www.everglades_holidaypark.com<br />
<br />
'''Solution:'''<br />
This Regular Expression matches a domain name used to access web sites.<br />
<br />
RE starts with the subdomain www, continues with a number of names of domains, separated by a dot (Top-level domain (TLD), Second-level domain (SLD), Third-level domain, and so on).<br />
<br />
The name of a domain contains only small letters, digits and hyphen. The name can’t begin and can’t finish with a hyphen character. The length of the domain’s name is minimum 2 and maximum 63 characters.<br />
<br />
'''^''': the string starts with '''www''', followed by a dot character;<br />
<br />
'''[a-z0-9]''' : the first and the last character of the domain's name can be only a small letter or a digit;<br />
<br />
'''[-a-z0-9]{0,61}''': the next characters can be small letters, digits or a hyphen character. Maximum 61 characters;<br />
<br />
The last sequence '''[a-z0-9][-a-z0-9]{0,61}[a-z0-9]''' is for the Top-Level domain, which is not followed by a dot.<br />
<br />
The strings that are represented by this pattern are 1, 4 and 6.<br />
<br />
= Video Resources =<br />
<br />
Nice two-part video showing the relationship between FSAs and REs. <br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/GwsU2LPs85U</youtube><br />
| [https://youtu.be/GwsU2LPs85U ''1 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]<br />
<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/shN_kHBFOUE</youtube><br />
| [https://youtu.be/shN_kHBFOUE ''2 - Convert Regular Expression to Finite-State Automaton'' ('''Barry Brown''')]<br />
<br />
This video uses the symbol "+" to mean "1 or more matches of the previous term". For example, "ab+" is the same as "abb*". In terms of the Kleene Star, zz* = z*z = z+.<br />
|}<br />
<br />
{|<br />
|-<br />
| <youtube width="300" height="180">https://youtu.be/vI_yv0WuAhk</youtube><br />
| [https://youtu.be/vI_yv0WuAhk ''ACSL Test Prep - Finite State Automaton & Regular Expressions Explained'' ('''Mrs. Gupta''')]<br />
<br />
A talked-over presentation discussing the finite state automatons and regular expressions as needed for the American Computer Science League and its tests. <br />
|}<br />
<br />
<!--<br />
{|<br />
|-<br />
| <youtube width="300" height="180">URL</youtube><br />
| [URL ''TITLE'' ('''AUTHOR''')]<br />
<br />
DESCRIPTION<br />
|}<br />
--></div>Janhttp://www.categories.acsl.org/wiki/index.php?title=Karnaugh_Maps&diff=714Karnaugh Maps2020-08-18T18:35:05Z<p>Jan: /* Introduction */</p>
<hr />
<div>= Introduction =<br />
Logic design implies the analysis, synthesis, minimization, and implementation of binary functions.<br />
Combinational logic refers to networks whose output is strictly dependent on the inputs. The analysis of such networks requires first the writing of the Boolean algebraic equation representative of the network, and then the complete characterization of the output as a result of all the possible combinations of the inputs.<br />
Minimization involves reducing the Boolean algebraic expression to some minimal form. <br /><br />
Any minimization tool in Boolean is based on the algebraic theorems. Algebraic reduction of Boolean functions is not easy and requires considerable experience, judgement and luck. It becomes more apparent as the complexity of the function increases. As a result extensive effort has been devoted toward developing techniques, aids or tools, that will allow the logic designer to minimize a function. The Venn diagram, Veitch diagram, Karnaugh map, Quine-McCluskey method, and other techniques have all been developed with but one objective-to allow the designed to arrive at a minimal expression as rapidly as possible with the least amount of effort.<br />
<br /><br />
Amoung these methods the Karnaugh Maps (made by G. Karnaugh in 1953) will be presented bellow.<br />
The '''Karnaugh map''' technique is thought to be the most valuable tool available for dealing with Boolean functions. It provides instant recognition of the basic patterns, can be used to obtain all possible combinations and minimal terms, and is easily applied to all varieties of complex problems. Minimization with the map is accomplished through recognition of basic patterns.<br /><br />
The appearance of 1’s in adjacent cells immediately identifies the presence of a redundant variable. <br /><br />
The following figures illustrate some examples of minimizing with a three-variable map and four-variable map.<sup>[1]</sup><br />
<br /><br />
<br />
= Karnaugh Map examples =<br />
<br />
{| class="wikitable"<br />
|-<br />
|<br />
[[File:T31.jpg|256px]]<br />
|| <br />
[[File:T32.jpg|256px]]<br />
||<br />
[[File:T33.jpg|256px]]<br />
|| <br />
[[File:T34.jpg|256px]]<br />
|-<br />
|-<br />
|<br />
[[File:T35.jpg|256px]]<br />
|| <br />
[[File:T36.jpg|256px]]<br />
||<br />
[[File:T37.jpg|256px]]<br />
|| <br />
[[File:T38.jpg|256px]]<br />
|-<br />
|-<br />
|<br />
[[File:T41.jpg|256px]]<br />
|| <br />
[[File:T42.jpg|256px]]<br />
||<br />
[[File:T43.jpg|256px]]<br />
|| <br />
[[File:T44.jpg|256px]]<br />
|-<br />
|-<br />
|<br />
[[File:T45.jpg|256px]]<br />
|| <br />
[[File:T47.jpg|256px]]<br />
||<br />
[[File:T48.jpg|256px]]<br />
|| <br />
[[File:T49.jpg|256px]]<br />
|-<br />
|-<br />
|<br />
[[File:T410.jpg|256px]]<br />
|| <br />
[[File:T411.jpg|256px]]<br />
||<br />
[[File:T412.jpg|256px]]<br />
|| <br />
[[File:T413.jpg|256px]]<br />
|-<br />
<br />
|}<br />
''' RULES SUMMARY'''<br /><br />
<br />
No zeros allowed.<br /><br />
<br />
No diagonals.<br /><br />
<br />
Only power of 2 number of cells in each group.<br /><br />
<br />
Groups should be as large as possible.<br /><br />
<br />
Every one must be in at least one group.<br /><br />
<br />
Overlapping allowed.<br /><br />
<br />
Wrap around allowed.<br /><br />
<br />
Fewest number of groups possible.<br /><br />
<br /><br />
= Sample problems =<br />
== Sample problem 1 ==<br />
''' Karnaugh Map to minimize a digital circuit '''<br />
{| class="wikitable"<br />
|-<br />
! Initial circuit !! Karnaugh Map !! AND/OR circuit<br />
|-<br />
<br />
|| [[File:CIR6_A.jpg|420px]] || [[File:T6n.jpg|250px]] || [[File:c6b.jpg|380px]]<br />
|}<br />
1. William E. Wickes, Logic Design with Integrated Circuits, John Willey & Sons, Inc, New York-London-Sydney</div>Jan