Prouver que l'ensemble des langues régulières est un sous-ensemble de l'ensemble des langues sans contexte

Question

je brossage (pas de devoirs) sur certains calcul théorie et ce problème tombé sur:

Comment pouvez-vous prouver que l'ensemble des langues régulières est un sous-ensemble de l'ensemble des langues sans contexte.

Maintenant, je sais une langue est régulière ssi il est accepté par un automate fini.

Et je sais que la langue est sans contexte ssi elle est acceptée par un pushdown automate.

Mais je ne suis pas sûr de ce que la solution est.

Answer 1

Tout DFA est équivalent à un PDA qui arrive de ne jamais pousser quoi que ce soit sur sa pile, donc toutes langues régulières sont également hors-contexte. Plus formellement:

A DFA est défini comme un 5-tuple (S, S, S0, d, F) constitué de l'alphabet d'entrée, ensemble d'états, commencer l'état, la table de transition, et ensemble d'états finaux (accepter).

Un PDA est défini comme un 7-tuple, y compris tous les éléments d'un DFA, ainsi que deux autres paramètres: Y (l'alphabet de pile) et Z (le symbole de pile initiale). Une table de transition PDA est quelque peu différente à partir d'une table de transition DFA: chaque transition peut dépendre à la fois le symbole d'entrée et le symbole de la pile en cours, et les transitions peuvent pousser ou pop de la pile.

Ainsi, en introduisant un alphabet de pile factice constitué d'un seul symbole, il est trivial (quoique un peu ennuyeux et de longue haleine pour écrire!) Pour cartographier la table de transition DFA (state, input) -> state à un équivalent tableau transition PDA (state, input, stack) -> (state, stack).

Pour compléter la preuve d'une relation de sous-ensemble: il existe des langages qui sont sans contexte, mais pas régulièrement, de sorte que les langues régulières forment un sous-ensemble des langues sans contexte. Exemple:. La langue des chaînes composées de parenthèses équilibrées