for the core part of assignment 9.  Please note all marks are provisional until

re.scala does not contain vars, returns, Arrays, ListBuffers etc?

re.scala runs?

 nullable(ZERO) == false

 nullable(ONE) == true

 nullable(CHAR('a')) == false

 nullable(ZERO | ONE) == true

 nullable(ZERO | CHAR('a')) == false

 nullable(ONE ~  ONE) == true

 nullable(ONE ~ CHAR('a')) == false

 nullable(STAR(ZERO)) == true

 der('a', ZERO | ONE) == (ZERO | ZERO)

 der('a', (CHAR('a') | ONE) ~ CHAR('a')) == ALT((ONE | ZERO) ~ CHAR('a'), ONE)

 der('a', (CHAR('a') | CHAR('a')) ~ CHAR('a')) == (ONE | ONE) ~ CHAR('a')

 der('a', STAR(CHAR('a'))) == (ONE ~ STAR(CHAR('a')))

 der('b', STAR(CHAR('a'))) == (ZERO ~ STAR(CHAR('a')))

 val r0 = "a" ~ "b" ~ "c"

 assert(der('a', r0) == (ONE ~ "b") ~ "c")

 assert(der('b', r0) == (ZERO ~ "b") ~ "c")

 assert(der('c', r0) == (ZERO ~ "b") ~ "c")

 val r1 = (ONE ~ "b") ~ "c"

 assert(der('a', r1) == ((ZERO ~ "b") | ZERO) ~ "c")

 assert(der('b', r1) == ((ZERO ~ "b") | ONE) ~ "c")

 assert(der('c', r1) == ((ZERO ~ "b") | ZERO) ~ "c")

 val r2 = ((ZERO ~ "b") | ONE) ~ "c"

 assert(der('a', r2) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO))

 assert(der('b', r2) == ((((ZERO ~ "b") | ZERO) ~ "c") | ZERO))

 assert(der('c', r2) == ((((ZERO ~ "b") | ZERO) ~ "c") | ONE))

 simp(ZERO | ONE) == ONE

 simp(STAR(ZERO | ONE)) == STAR(ZERO | ONE)

 simp(ONE ~ (ONE ~ (ONE ~ CHAR('a')))) == CHAR('a')

 simp(((ONE ~ ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')

 simp(((ONE | ONE) ~ ONE) ~ CHAR('a')) == CHAR('a')

 simp(ONE ~ (ONE ~ (ONE ~ ZERO))) == ZERO

 simp(ALT(ONE ~ (ONE ~ (ONE ~ ZERO)), CHAR('a'))) == CHAR('a')

 simp(CHAR('a') | CHAR('a')) == CHAR('a')

 simp(CHAR('a') ~ CHAR('a')) == CHAR('a') ~ CHAR('a')

 simp(ONE | CHAR('a')) == (ONE | CHAR('a'))

 simp(ALT((CHAR('a') | ZERO) ~ ONE,

          ((ONE | CHAR('b')) | CHAR('c')) ~ (CHAR('d') ~ ZERO))) == CHAR('a')

 simp((ZERO | ((ZERO | ZERO) | (ZERO | ZERO))) ~ ((ONE | ZERO) | ONE ) ~ (CHAR('a'))) == ZERO

 simp(ALT(ONE | ONE, ONE | ONE)) == ONE

 simp(ALT(ZERO | CHAR('a'), CHAR('a') | ZERO)) == CHAR('a')

 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

 ders(("a" * 5).toList,EVIL) == SEQ(SEQ(STAR(CHAR('a')),STAR(STAR(CHAR('a')))),CHAR('b'))

 ders(List('b'),EVIL) == ONE

 ders(List('b','b'),EVIL) == ZERO

 matcher(EVIL, "a" * 5 ++ "b") == true

 matcher(EVIL, "a" * 50 ++ "b") == true

 matcher(EVIL, "a" * 50) == false

 matcher(EVIL, "b") == true

 matcher(EVIL, "bb") == false

 matcher("abc", "abc") == true

 matcher("abc", "ab") == true

 matcher(("ab" | "a") ~ (ONE | "bc"), "abc") == true

 matcher(ONE, "") == true

 matcher(ZERO, "") == false

 matcher(ONE | CHAR('a'), "") == true

 matcher(ONE | CHAR('a'), "a") == true

  --> success

 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

 size(der('a', der('a', EVIL))) == 28

 size(der('a', der('a', der('a', EVIL)))) == 58

 size(ders("aaaaaa".toList, EVIL)) == 8

 size(ders(("a" * 50).toList, EVIL)) == 8

  --> success

 simp(Iterator.iterate(ONE:Rexp)(r => SEQ(r, ONE | ONE)).drop(50).next) == ONE

    ...the Iterator produces the rexp

      SEQ(SEQ(SEQ(..., ONE | ONE) , ONE | ONE), ONE | ONE)

    where SEQ is nested 50 times.

 simp(Iterator.iterate(ONE:Rexp)(r => ALT(r, r)).drop(20).next) == ONE

    ... the Iterator produces a rexp of size 2097151

 val EVIL = SEQ(STAR(STAR(CHAR('a'))), CHAR('b'))

 matcher(EVIL, "a" * 1000000 ++ "b") == true

 matcher(EVIL, "a" * 1000000) == false

  --> success

Overall mark for CW 9, Core Part

6