程序代写代做代考 CS314 Fall 2018 Assignment1 Solution

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