CS314 Fall 2018 Assignment1 Solution
September 2018
1 Rewrite System
a) 01 =⇒ ε
10 =⇒ ε
b) No, in some scenarios, it is possible that multiple rules can be applied.
E.g. using the two rules in a) and the the input sequence $1001#, if we
use 01 =⇒ ε, we can get $10#. But if we use 10 =⇒ ε, we get $01#.
c) $0101# use rule 01 =⇒ ε
$01# use rule 01 =⇒ ε
$# no rules
$10110# use rule 10 =⇒ ε
$110# use rule 10 =⇒ ε
$1# no rules
1
2 Regular Expressions
C const =⇒ int const|fp const
int const =⇒ (oct int|dec int|hex int)int suffix
fp const =⇒ (dec fp|hex fp)fp suffix
oct int =⇒ 0 nonzero oct digit oct digit∗
dec int =⇒ nonzero dec digit dec digit∗
hex int =⇒ (0x|0X) nonzero hex digit hex digit∗
dec fp =⇒ sign dec digit dec digit∗ dec exponent| sign dec digit∗
(.dec digit|dec digit.) dec digit∗ (dec exponent|ε)
hex fp =⇒ sign (0x|0X) hex digit∗(.hex digit|ε|hex digit.)hex digit∗
hex exponenet
int suffix =⇒ ε| unsigned suffix(long suffix|longlong suffix|ε)|
long suffix(unsigned suffix|ε)| longlong suffix(unsigned suffix|ε)
fp suffix =⇒ float suffix|long suffix|ε
nonzero oct digit =⇒ 1|2|3|4|5|6|7
nonzero dec digit =⇒ nonzero oct digit|8|9
nonzero hex digit =⇒ nonzero dec digit|a|b|c|d|e|f |A|B|C|D|E|F
oct digit =⇒ 0|nonzero oct digit
dec digit =⇒ 0|nonzero dec digit
hex digit =⇒ 0|nonzero hex digit
sign =⇒ ε|+ |−
dec exponent =⇒ (e|E)sign dec digit dec digit∗
hex exponent =⇒ (p|P )sign dec digit dec digit∗
unsigned suffix =⇒ u|U
long suffix =⇒ l|L
longlong suffix =⇒ ll|LL
float suffix =⇒ f |F
2
3 Regular Expressions
a) All binary strings, including the empty string.
b) All binary strings of length ≥ 3, with 1 as the third to the last digit.
c) All binary strings of even number of 0’s and 1’s
4 Regular Expressions
a) (a|c)∗(b|c)∗
Please be careful about the difference between ”no a’s following b’s” and
”no a’s immediately following b’s”.
b) c∗(a|ε)c∗(a|ε)c∗(b|ε)c∗(b|ε)c∗|
c∗(a|ε)c∗(b|ε)c∗(a|ε)c∗(b|ε)c∗|
c∗(a|ε)c∗(b|ε)c∗(b|ε)c∗(a|ε)c∗|
c∗(b|ε)c∗(a|ε)c∗(a|ε)c∗(b|ε)c∗|
c∗(b|ε)c∗(a|ε)c∗(b|ε)c∗(a|ε)c∗|
c∗(b|ε)c∗(b|ε)c∗(a|ε)c∗(a|ε)c∗
3