CODEWITHSUNDEEP
scalaautomatapushdown-automaton
Youngheon Jeong
Youngheon Jeong

Reputation: 11

Push Down Automata for the language L = { a^i b^j c^k | i, j, k >= 0 and j = i + 2k }

I drew PDA diagram for this language but it still does not work. Can some please help me? My PDA accepts 'bc' which it should not. I have no idea to control the b and c of the language. My scala code for the pda is below.

PDA = PDA(
    states = Set(0, 1, 2, 3),
    symbols = Set('a', 'b', 'c'),
    alphabets = Set("A", "B"),
    trans = Map(
      (0, Some('a'), "Z") -> Set((0, List("A", "Z"))),
      (0, Some('a'), "A") -> Set((0, List("A", "A"))),
      (0, None, "Z") -> Set((3, List("Z"))),

      (0, Some('b'), "A") -> Set((1, List())),
      (0, Some('b'), "Z") -> Set((1, List("B", "Z"))),

      (1, Some('b'), "A") -> Set((1, List())),
      (1, Some('b'), "Z") -> Set((1, List("B", "Z"))),
      (1, Some('b'), "B") -> Set((1, List("B", "B"))),
      

      (1, None, "Z") -> Set((3, List("Z"))),

      (1, Some('c'), "B") -> Set((2, List())),

      (2, Some('c'), "B") -> Set((2, List())),

      (2, None, "Z") -> Set((3, List("Z"))),
    ).withDefaultValue(Set()),
    initState = 0,
    initAlphabet = "Z",
    finalStates = Set(3),
  )

enter image description here

Upvotes: 1

Views: 1204

Answers (1)

Nathan
Nathan

Reputation: 21

You currently have a pda for the language L = {a^i b^j c^k | j = i + k}

To change it to the language you want, you have to change the transitions

(0, Some('b'), "Z") -> Set((1, List("B", "Z"))),

(1, Some('b'), "B") -> Set((1, List("B", "B"))),

to

(0, Some('b'), "Z") -> Set((1, List("B", "B", "Z"))),

(1, Some('b'), "B") -> Set((1, List("B", "B", "B"))),

Upvotes: 1

Related Questions