Theory: A deterministic PDA for wcwᴿ

Recognise a context-free language with a deterministic pushdown automaton.

What to build

A program that accepts strings w c wᴿ over {a, b}: a word, the marker c, then the word reversed.

Requirements

  • Simulate the PDA: a push phase until c, then a pop phase.
  • Print yes or no for each word.

Input

Line 1: n. Then n words over {a, b, c} (a word may be an empty line).

Output

n lines.

Constraints

n ≤ 20; words have at most 40 symbols.

Example

Input:

3
abcba
abcab
c

Output:

yes
no
yes

Why it works

The marker tells the machine where the middle is, so one pass with a stack is enough, with no guessing.

Examples

Example 1 · Input
3
abcba
abcab
c
Expected output
yes
no
yes
Example 2 · Input
2
bacab
ab
Expected output
yes
no

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Push every symbol before the c; after the c, pop and compare with each symbol.

Hint 2

Reject if there is no c, a second c, a mismatch, or symbols left on the stack.

Solution

Show one correct solution (try it yourself first)
for _ in range(int(input())):
    word = input()
    stack = []
    phase = "push"
    ok = True
    for c in word:
        if phase == "push":
            if c == "c":
                phase = "pop"
            else:
                stack.append(c)
        elif c == "c" or not stack or stack.pop() != c:
            ok = False
            break
    print("yes" if ok and phase == "pop" and not stack else "no")

Lesson: Pushdown automata →