simple CYK algorithm implementation

CYK.scala

case class Grammar(V: Set[Char],
                   Σ: Set[Char],
                   P: List[(Char, String)],
                   S: Char)

object CYK {
  def cartesian(as: Array[Char], bs: Array[Char]): Array[String] = {
    for {a <- as; b <- bs} yield (a.toString + b.toString)
  }

  def apply(word: String, G: Grammar): Boolean = {
    val n = word.length
    val T = Array.fill(n, n)("")

    word.zipWithIndex foreach {
      case (c: Char, i: Int) =>
        T(i)(0) = G.P.filter(_._2 == c.toString).map(_._1).mkString
    }

    2 to n foreach { j =>
      1 to (n - j + 1) foreach { i =>
        1 to (j - 1) foreach { k =>
          // could consist of 2 non terminal, so we have to test every combination
          val first = T(i - 1)(k - 1).toCharArray
          val second = T(i + k - 1)(j - k - 1).toCharArray

          cartesian(first, second) foreach { nonTerminalCombination =>
            T(i - 1)(j - 1) = T(i - 1)(j - 1) + G.P
              .filter(_._2 == nonTerminalCombination)
              .map(_._1)
              .mkString
          }
        }
      }
    }

    println(T.map(_.zipWithIndex.mkString("\t")).mkString("\n"))

    T(0)(n - 1).contains("S")
  }
}

Main.scala

object Main extends App {
  val G = Grammar(
    V = Set('S', 'A', 'F', 'C', 'E', 'B', 'D'),
    Σ = Set('a', 'b', 'c'),
    S = 'S',
    P = List('S' -> "AB",
      'A' -> "CD",
      'A' -> "CF",
      'B' -> "EB",
      'F' -> "AD",
      'B' -> "c",
      'C' -> "a",
      'D' -> "b",
      'E' -> "c")
  )

  val word = "aaabbbc"
  val result = CYK(word, G)

  result match {
    case true =>
      println(s"'$word' is element of L(G)")
    case false =>
      println(s"'$word' is NOT element of L(G)")
  }
}