Crie um PDA para o idioma dado

Question

A tarefa é criar um PDA para este idioma.O | u | uma refeição para o número de A nessa palavra.Eu tentei trabalhar nisso como dois idiomas separados que posso combinar mais tarde, mas não conseguir fazer qualquer um dos dois.

Eu apreciaria qualquer ajuda.

Answer 1

Como você menciona divisão $ l $ em dois idiomas diferentes e combinando os PDAs resultantes, eu suponho que você está bem com PDAs não-intermináveis.

Deixe-me mostrar-lhe uma gramática sem contexto para $ l $ em vez disso (há maneiras padrão e completamente mecânicas de converter gramáticas CFG para PDAs).

Deixe $ \ sigma= {a, b, c \} $ e split $ l $ em dois idiomas $ l_1= {uv \ in \ sigma ^ *: 3 | u | _a= | v | _b + | v | _c \} $ e $ l_2= {UV \ in \ sigma ^ *: | u | _c= 2 | v | _a \} $ . Podemos então projetar uma gramática sem contexto para $ l_1 $ e $ l_2 $ separadamente.

Um CFG para $ l_1 $ é o seguinte (onde o axioma é $ s_1 $ ): $$ \ começo {alinhar *} S_1 & \ to xs_1a \ meados as_1yayay \ meados \ epsilon \\ X & \ to bx \ meados cx \ meados \ epsilon \\ A & \ para AA \ Mid \ Epsilon \\ Y & \ para b \ meados c \ final {alinhar *} $$

um CFG para $ l_2 $ é o seguinte (onde o axioma é $ s_2 $ ): $$ \ começo {alinhar *} S_2 & \ to ws_2z \ meados cwcs_2a \ mid \ epsilon \\ W & \ to AW \ MID BW \ MID \ EPSILON \\ Z & \ para bz \ meados cz \ meados \ epsilon \ final {alinhar *} $$

Para obter uma gramática para $ l $ , é suficiente combinar as duas primeiras gramáticas e adicionar a produção $ s \ to s_1 \ meados s_2 $ (onde $ s $ é o novo axioma).