La langue suivante est le complément d'une langue plus simple. Construire un DFA pour le langage le plus simple, puis l'utiliser pour donner le diagramme d'état d'un DFA pour la langue donnée où Σ = {a, b}. L = {w: w ne contient pas la sous-chaîne baba}Comment déterminer quelle langue est la plus simple
Je ne sais pas quelle est la langue la plus simple, quelqu'un peut-il expliquer?
Les automates acceptant un mot contenant la sous-chaîne 'baba' est:
(c'est la langue plus simple Une expression rationnelle car il est:. (A | b) * BABA (a | b) *)
et nous pouvons construire le complément DFA en tournant les Etats qui acceptent en non-acceptation et vice-versa comme vous mentionnais il:
(il doit être complété)
Cela fait un certain temps que ma classe de calcul de la logique &, mais je suppose que le langage complémentaire Lc serait = {w: w contient la sous-chaîne 'baba'}.
Il est probablement assez facile de créer un DFA qui accepte les sous-chaînes de 'baba', vous auriez probablement juste les états firstB, firstA, secondB et secondA et ainsi de suite.
Faire un complément DFA est alors trivial, il suffit de rendre les états accepteurs non-acceptants et vice versa.
Ainsi est ce que l'on entend par "langage plus simple" est {w: w contient la sous-chaîne 'baba'}. à partir de laquelle je vais transformer les états acceptant en n'acceptant pas et vice versa comme vous l'avez mentionné ?? – nmorsi
merci beaucoup .. l'état 5 est omis parce que c'est un état mort ou inaccessible, non? – nmorsi
oui, c'est un état mort. vous pouvez l'ajouter pour obtenir un DFA complet –