CODEWITHSUNDEEP
context-free-grammarautomatonpushdown-automaton
Charles Del Lar
Charles Del Lar

Reputation: 85

A pushdown automaton that recognizes the negation of a language

As an example:

Say I want to design a PDA that recognizes the language of all strings over the alphabet {1,0} that are NOT palindromes. If I design a PDA that recognizes the language of all strings over the {1,0} that are palindromes and then swap all accept states for fail states and vice versa will I get the desired PDA?

EDIT: Is there a simple formal proof either way?

Upvotes: 0

Views: 3748

Answers (1)

rici
rici

Reputation: 241881

The set of context-free languages (or PDAs) is not closed under complementation. (There's a simple demonstration in the answer to What is the context free grammar for the complement of the double word over 0,1?, which constructs a CFG for the complement of {ww|w∈{0,1}*}. The fact that {ww|w∈{0,1}*} is not a CFL is well known.)

Inverting all the states of a state machine works fine for a finite-state automaton (and regular languages are closed under complement), but it won't work for a PDA precisely because of the stack.

Upvotes: 2

Related Questions