Je travaille à travers un exercice difficile dans un manuel, et je n'arrive pas à comprendre comment procéder. Voici le problème. Supposons que nous ayons le langage L = { a i b j : i ≤ j γ , i ≥ 0 , j ≥ 1 }L={aibj:i≤jγ,i≥0,j≥1}L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\} où γγ\gamma est un...
Je sais que les langages qui peuvent être définis à l'aide d'expressions régulières et ceux reconnaissables par DFA / NFA (automates finis) sont équivalents. De plus, aucun DFA n'existe pour la langue . Mais il peut encore être écrit en utilisant des expressions régulières (pour cette question...
Décrivez une langue régulière qui ne peut être acceptée par aucun DFA qui ne comporte que trois états. Je ne sais pas trop par où commencer et je me demandais si quelqu'un pourrait me donner quelques conseils ou astuces. Je comprends que le lemme de pompage peut être utilisé pour prouver qu'une...
Je commence tout juste à entrer dans la théorie du calcul, qui étudie ce qui peut être calculé, à quelle vitesse, en utilisant la quantité de mémoire et avec quel modèle de calcul. J'ai une question assez basique, mais j'espère vraiment que certains d'entre vous pourront m'aider à comprendre le...
La question est à peu près dans le titre. Y a-t-il jamais un moment où une langue peut être acceptée par un DFA minimal avec états, mais , l'inversion de , peut être acceptée par un DFA avec états, où ?LLLL R L m m < nnnnLRLRL^RLLLmmmm <
Je travaille avec un algorithme de correspondance de motifs qui génère un automate à états finis acyclique qui accepte une chaîne de texte donnée et toutes ses sous-chaînes. L'algorithme FSA est exécuté sur une représentation symbolique d'un flux musical (par exemple, des données MIDI). Le flux...
Une façon de regarder les expressions régulières est une preuve constructive du fait suivant: il est possible de construire les langages réguliers en commençant par un petit ensemble de langages et en les combinant via un petit ensemble fixe de propriétés de fermeture. Plus précisément, si nous...
Je me demandais récemment ce qui se passerait si nous permettions aux grammaires sans contexte d'avoir un nombre infini de règles. De toute évidence, si nous permettions arbitrairement de tels ensembles infinis de règles, chaque langue sur un alphabet pourrait être décrite par un CFG avec . Mais...
J'ai commencé à étudier les automates non déterministes en utilisant le livre de Hopcroft et Ullman . Je suis coincé dans un problème que j'ai trouvé très intéressant: Donnez un automate fini non déterministe acceptant toutes les chaînes qui ont la même valeur lorsqu'elles sont évaluées de gauche à...
Je suis coincé à résoudre le prochain exercice: Faire valoir que si est sans contexte et R est régulier, alors L / R = { w ∣ ∃ x ∈ RLLLRRR (c'est-à-dire lebon quotient) est sans contexte.L/R={w∣∃x∈Rs.twx∈L}L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Je sais qu'il...
Étant donné un langage , comment dire directement, sans regarder les règles de production, que ce langage n'est pas régulier?L={anbncn}L={anbncn} L= \{a^n b^n c^n\} Je pourrais utiliser le lemme de pompage mais certains gars disent juste en regardant la grammaire que ce n'est pas normal. Comment...
Dans l'article Parsing Expressions by Recursive Descent de Theodore Norvell (1999), l'auteur commence par la grammaire suivante pour les expressions arithmétiques: E --> E "+" E | E "-" E | "-" E | E "*" E | E "/" E | E "^" E | "(" E ")" | v ce qui est assez mauvais, car il est ambigu et...
J'ai passé ma théorie des examens de calcul il y a quelques semaines, et c'était l'une des questions: Supposons que la langueL={(anbm)r∣n,m,r≥0}L={(anbm)r∣n,m,r≥0}L=\{(a^nb^m)^r \mid n,m,r\ge 0\} L est-il régulier? Si oui, fournissez-lui une expression régulière ou un automate. Après que je lui ai...
Récemment, j'ai posé une question sur Math SE. Pas encore de réponse. Cette question est liée à cette question, mais plus de détails techniques vers l'informatique. Étant donné deux DFA et B = ( Q , Σ , δ , q 2 , F 2 ) où l'ensemble des états, l'alphabet d'entrée et la fonction de transition de A...
J'ai lu des articles théoriques sur le langage formel et je suis tombé sur un terme que je ne comprends pas. Le document fera souvent référence à un ensemble «effectivement fermé sous intersection» ou à d'autres opérations. Que signifie "effectivement" ici? En quoi cela diffère-t-il de la fermeture...
Je recherche une grammaire contextuelle qui décrit le langage suivant: .L={ww∣w∈{a,b}∗,|w|≥1}L={ww∣w∈{a,b}∗,|w|≥1}L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\} J'ai des problèmes avec le fait qu'aucune règle comme n'est autorisée et donc je ne peux placer aucun terminal indiquant le "milieu" du mot....
Étant donné une langue régulière infinie LLL, comment puis-je prouver que LLL peut être partitionné en 2 langages réguliers infinis disjoints L1,L2L1,L2L_1, L_2? C'est:L1∪L2=LL1∪L2=LL_1 \cup L_2 = L, L1∩L2=∅L1∩L2=∅L_1 \cap L_2 = \varnothing, et L1L1L_1 et L2L2L_2 sont à la fois infinies et...
Habituellement, je vois que dans la représentation sémantique opérationnelle structurelle pour la boucle while, l'état du programme ne change pas: ( W h i l eBréoS, σ) → ( i fBt h e nS; ( W h i l eBréoS)e l s eSKjeP, σ)(whileBdoS,σ)→(ifBthenS;(whileBdoS)elseSKIP,σ)(while \> B \> do \>S, \sigma)...
J'ai récemment discuté avec un ami d'un site Web qui proposait des défis d'expression régulière, correspondant principalement à un groupe de mots avec une propriété spéciale. Il cherchait une expression régulière qui correspond à des chaînes comme ||||||||où le nombre de |est premier. Je lui ai...
Un langage formel sur un alphabet Σ est un sous-ensemble de Σ ∗ , c'est-à-dire un ensemble de mots sur cet alphabet. Deux langages formels L et L ′ sont égaux, si les ensembles correspondants sont extensionnellement égaux en tant que sous-ensembles de L ∪ L ′ . On peut utiliser les langages dans la...