| |
Below, "ST" stands for "Set Theory", "RE" stands for "Regular Expression",
and "IN" stands for "Informal".
1.a) A ==> a A c ==> a a A c c ==> a a b c c
A ==> a A c ==> a b c
A ==> b
IN: The sentences consist of one 'b' preceded by an number n >= 0 of 'a's and
followed by the same number n of 'c's, or
ST: {anbcn: n >= 0}, or
RE: Can't be done.
b) O ==> a E ==> a a O ==> a a a
O ==> a
O ==> a E ==> a a O ==> a a a E ==> a a a a O ==> a a a a a
("E" stands for "even" and "O" stands for "odd".)
IN: There will always be an odd number ( >= 1) of 'a's, or
ST: {an: n >= 1, n odd}, or
RE: /a(aa)*/
c) L ==> L A ==> L A A ==> A A A ==> a A A ==> a a A ==> a a a
L ==> A ==> a
L ==> L A ==> A A ==> a A ==> a a
IN: Any number n >= 1 of 'a's, or
ST: {an: n >= 1}, or
RE: /a+/
d) N ==> ( C ) ==> ( C , A ) ==> ( C , A , A ) ==> ( C , A , A , A ) ==>
( A , A , A , A ) ==> ( a , A , A , A ) == > ( a , b , A , A ) ==>
( a , b , c , A ) ==> ( a , b, c , d )
N ==> ( C ) ==> ( A ) ==> ( a )
n ==> ( C ) ==> ( C , A ) ==> ( A , A ) ==> ( a , A ) ==> ( a , c )
IN: There will always be at least one 'a' 'b' 'c' or 'd' inside of a set of
parenthesis and if more than one, they are separated by commas, or
RE: /\(((a|b|c|d),)*(a|b|c|d)\)/
(see below for a Python test of the RE)
e) S ==> A B ==> a A B ==> a a B ==> a a b B c ==> a a b b c c
S ==> A B ==> a B ==> a b c
S ==> A B ==> a B ==> a b B c ==> a b b c c
IN: Any number n >= 1 of 'a's followed by any number m >= 1 of 'b's, and
the same number m of 'c's, or
ST: {anbmcm: n >= 1, m >= 1}.
RE: Can't be done.
2.a) E ==> E * E ==> a * E ==> a * ( E ) ==> a * ( E + E ) ==> a * ( b + E )
==> a * ( b + c )
E
/|\
E * E
/ /|\
a ( E )
/|\
E + E
| |
b c
b) E ==>
E + E ==>
E * E + E ==>
a * E + E ==>
a * b + E ==>
a * b + c
E ==>
E * E ==>
a * E ==>
a * E + E ==>
a * b + E ==>
a * b + c
E E
/|\ /|\
E + E E * E
/|\ \ / /|\
E * E c a E + E
| | | |
a b b c
3.a)
E ==>
E + T ==>
E + T + T ==>
T + T + T ==>
F + T + T ==>
a + T + T ==>
a + F + T ==>
a + b + T ==>
a + b + F ==>
a + b + c
E
/|\
E + T
/|\ \
E + T F
/ \ \
T F c
| |
F b
|
a
b) E ==>
E + T ==>
T + T ==>
T * F + T ==>
F * F + T ==>
a * F + T ==>
a * b + T ==>
a * b + T * F ==>
a * b + F * F ==>
a * b + c * F ==>
a * b + c * d
E
/|\
E + T
/ /|\
T T * F
/|\ | |
T * F F d
| | |
F b c
|
a
4.a) Terminals: = + - * / ^ ( ) a b c d
Non-Terminals: A E T S F L
Metasymbols: --> |
b.i) A ==>
L = E ==>
d = E ==>
d = T ==>
d = S ==>
d = F ^ S ==>
d = L ^ S ==>
d = a ^ S ==>
d = a ^ F ^ S ==>
d = a ^ L ^ S ==>
d = a ^ b ^ S ==>
d = a ^ b ^ F ==>
d = a ^ b ^ L ==>
d = a ^ b ^ c
A
/|\
L = E
/ |
d T
|
S
/|\
F ^ S
/ /|\
L F ^ S
/ | |
a L F
| |
b L
|
c
b.ii) A ==>
L = E ==>
d = E ==>
d = E + T ==>
d = T + T ==>
d = S + T ==>
d = F + T ==>
d = L + T ==>
d = a + T ==>
d = a + T * S ==>
d = a + S * S ==>
d = a + F * S ==>
d = a + L * S ==>
d = a + b * S ==>
d = a + b * F ^ S ==>
d = a + b * L ^ S ==>
d = a + b * c ^ S ==>
d = a + b * c ^ F ==>
d = a + b * c ^ L ==>
d = a + b * c ^ d
A
/|\
L = E
/ /|\
d E + T
/ /|\
T T * S
| | /|\
S S F ^ S
| | | |
F F L F
| | | |
L L c L
| | |
a b d
c) The first tree shows that ^ associates from right to left, that is,
that a^b^c = a^(b^c). The other 4 ops associate from left to right.
The second tree shows that ^ has higher precedence (is carried out
earlier) that any of the other 4 operators.
5 <double> ==>
<digit-list> <decimal part> <exp> ==>
<digit> <decimal part> <exp> ==>
2 <decimal part> <exp> ==>
2. <digit-list> <exp> ==>
2. <digit> <digit-list> <exp> ==>
2.4 <digit-list> <exp> ==>
2.4 <digit> <exp> ==>
2.45 <exp> ==>
2.45E <sign> <digit-list> ==>
2.45E- <digit-list> ==>
2.45E- <digit> ==>
2.45E-3
<double>
|
+---------------+--------------+----------+
| | |
<digit-list> <decimal part> <exp>
| | |
<digit> +----+--+ +----+----+-----+
| | | | | |
2 . <digit-list> E <sign> <digit-list>
| | |
+-------+--+ - <digit>
| | |
<digit> <digit-list> 3
| |
4 <digit>
|
5
6.a) (Leaving off <> from <id> and <const>.)
<stat> ==>
<if_stat> ==>
if ( <exp> ) <stat> ==>
if ( id ) <stat> ==>
if ( id ) <cmpd_stat> ==>
if ( id ) { <stat_list> } ==>
if ( id ) { <stat> } ==>
if ( id ) { <iter_stat> } ==>
if ( id ) { while ( <exp> ) <stat> } ==>
if ( id ) { while ( id ) <stat> } ==>
if ( id ) { while ( id ) <assgn_stat> } ==>
if ( id ) { while ( id ) id = <exp> ; } ==>
if ( id ) { while ( id ) id = <exp> <op> <exp> ; } ==>
if ( id ) { while ( id ) id = id <op> <exp> ; } ==>
if ( id ) { while ( id ) id = id + <exp> ; } ==>
if ( id ) { while ( id ) id = id + const ; }
<stat>
|
<if_stat>
|
+---+---+---+-----+
| | | | |
if ( <exp> ) <stat>
| |
id <cmpd_stat>
|
+------+------+
| | |
{ <stat_list> }
|
<stat>
|
<iter_stat>
|
+----+---+---+---+
| | | | |
while ( <exp> ) <stat>
| |
id <assgn_stat>
|
+--+--+-+---+
| | | |
id = <exp> ;
|
+------+-------+
| | |
<exp> <op> <exp>
| | |
id + const
% python regular2.py
RegExp-->(\(((a|b|c|d),)*(a|b|c|d)\))
String-->(a,b,c)
Inputs: RegExp: |(\(((a|b|c|d),)*(a|b|c|d)\))|
String: |(a,b,c)|
Search: group(0):|(a,b,c)|,
group(1):|(a,b,c)|
RegExp-->(\(((a|b|c|d),)*(a|b|c|d)\))
String-->(a,c,a,c,d,b,b)
Inputs: RegExp: |(\(((a|b|c|d),)*(a|b|c|d)\))|
String: |(a,c,a,c,d,b,b)|
Search: group(0):|(a,c,a,c,d,b,b)|,
group(1):|(a,c,a,c,d,b,b)|
|