Expressions régulières et automates

Question

J'étudie les expressions régulières en lisant le livre d'Aho. Je ne comprends pas deux des déclarations contenues dans le livre:

Question A:

1(0+1)*1 + 1 : denotes the set of all strings beginning and ending with a 1. 

Ma question est pourquoi +1 ajouté à la fin de l'expression régulière? Ne devrait pas 1(0+1)*1 être suffisant?

---

Je suis aussi des problèmes avec les éléments suivants:

Question B:

L'ensemble des chaînes contenant seulement 0 et de 1 qui ont atmost un 1 ci-dessous

0*+0*10* 

Pouvez-vous exp comment est arrivée la solution 0*+0*10*, étape par étape?

Answer 1

Pour la question a: 1(0+1)*1 INDIQUE ensemble de toutes les chaînes commençant et se terminant par une, mais ne contient pas de chaîne 1 qui a longueur et commence et se termine par un.

Pour la question b: Jeu de cordes contenant atmost un 1 = A + B où A est un ensemble de toutes les chaînes contenant zéro 1 s et B est l'ensemble de toutes les chaînes contenant exactement un 1

So A est 0* et B est 0*10* Par conséquent nous obtenons la réponse comme 0* + 0*10*

Answer 2

En ce qui concerne la question a: 1 (0 + 1) * 1 ne correspond pas à la chaîne d'un caractère 1, qui commence et se termine par 1. On a besoin d'un cas particulier, ce que fait l'exemple. En ce qui concerne la question b: je ne peux pas parler pour l'auteur. Cependant ... Toute chaîne qui contient au plus un 1 est une chaîne qui n'a pas de 1 ou qui en a exactement 1. En supposant que l'alphabet est {0,1}, le premier signifie toute chaîne qui contient zéro ou plus de 0, est, 0 *. Ce dernier, avec la même supposition, signifie toute chaîne qui contient zéro ou plus de 0 suivis par un 1 suivi de zéro ou de mpre 0, c'est-à-dire 0 * 10 *. La combinaison de ces résultats donne l'exemple.

Answer 3

Pour le premier exemple, la chaîne acceptée par le + 1 mais pas par le reste est 1. Le reste des expressions peut gérer 11, mais pas une chaîne où le premier et le dernier caractère sont les mêmes.

Le raisonnement est similaire pour la deuxième chaîne - 0 * gère les chaînes de tous les zéros, 0 * 10 * gère les chaînes de 1 unité.