Construa um PDA para o complemento de

16

Gostaria de saber se isso é possível, já que . Portanto, um PDA que pode distinguir uma palavra do resto de pode aceitá-la , o que me parece contraditório. w { um n b n c n | n 0 } { um * b * c * }{anbncnn0}CFLw{anbncnn0}{umabc}

Acho que preciso tirar proveito da natureza não determinística dos PDAs, mas estou sem ideias. Se você pudesse oferecer alguns conselhos, eu agradeceria muito.

hauptbenutzer
fonte
Ponto interessante sobre isso parecer contraditório. De fato, as linguagens sem contexto não são fechadas ao aceitar o complemento ... portanto, existem muitos exemplos de linguagens sem contexto que podem ser "aceitas" no sentido em que você alude. Eu não sou um teórico e, como tal, não consigo conciliar isso de verdade, mas talvez alguém possa conversar sobre por que isso não é algo para se preocupar?
precisa saber é o seguinte
Observe que isso generaliza: o complemento de é um CFG. {umanbncndnen}
Sdcvvc

Respostas:

15

Não, isso é livre de contexto. Para aceitar umanbncn , você precisa garantir que três números sejam iguais. Para aceitar umabcumanbncn , você só precisa ter certeza de que você está em um dos três casos seguintes:

  1. O número de s é diferente do número de b s; ouumab
  2. O número de s é diferente do número de c s; ouumac
  3. O número de s é diferente do número de c s.bc

Escreva um PDA para cada um desses casos e, em seguida, combine-os saltando não-deterministicamente para cada um a partir do estado inicial.

Patrick87
fonte
Eu escrevi esses casos, mas estava faltando a ideia de conectá-los. Obrigado!
hauptbenutzer
4
Na verdade, você precisa apenas de dois casos.
Sdcvvc
@sdcvvc Good point. :)
Patrick87
Para um número diferente de caracteres, considere isso como inspiração: . Deve ser simples colar um + à esquerda deste ou c + à direita e transformá-lo em um PDA. Para o caso complicado (do qual você não precisa) S a S c | Um | C ; A a B |SxSy|X|Y;Xx|xX;Yy|yYuma+c+ . SumaSc|UMA|C;UMAumaB|umaUMA;CBc|Cc;Bε|bB
Jonas Kölker 31/07