Prouver qu'une langue est régulière en donnant une expression régulière

Je suis déconcerté par ce problème de pratique (pas pour les marques):Prouver qu'une langue est régulière en donnant une expression régulière

{w est un élément de {a, b} *: le nombre de c'est même et le nombre de b est pair}

Je n'arrive pas à comprendre cela. Dans ce cas, 0 est considéré pair. Quelques chaînes acceptables: {}, {aa}, {bb}, {aabb}, {abab}, {bbaa}, {babaabba}, et ainsi de suite

J'ai fait des exemples similaires où le doit être un préfixe, où la réponse serait: (aa) (bb) mais dans ce cas ils peuvent être dans n'importe quel ordre.

Les étoiles de Kleene (*), les unions (U), recoupent (&), et la concaténation peut être utilisée.

Edit: ont aussi des problèmes avec celui-ci

{w est un élément de {0,1} *: w = 1^r 0 1^s 0 pour certains r, s> = 1}

Source

2010-10-05 Bobby S

Je ne vois pas une question .. – Kevin

@Kevin c'est dans le titre –

@Kevin Il veut une regex qui accepte une chaîne de a et b où le nombre des deux est pair. – NullUserException

est un peu laid, mais il devrait fonctionner:

ε U ((aa) U (bb) U ((ab) U (ba) (ab) U (ba)))*

Pour le second:

11*011*0

en général, j'utiliseraient a+ au lieu de aa* ici.

Source

2010-10-05 21:55:39 NullUserException

Basé sur le phrasé/les symboles, cela provient probablement d'un livre de théorie, et beaucoup d'entre eux n'introduisent pas réellement le métacaractère '+ '. Strictement parlant, cela ne fait pas partie de la théorie des ER, mais l'étoile Kleene est. Quoi qu'il en soit, '+ 'est juste du sucre syntaxique pour' aa * ', similaire à comment' a? 'Est sémantiquement le même que' u ε' – eldarerathis

@elderathis Ouais, quand j'ai pris la théorie des automates j'avais le '+' :) – NullUserException

@NullUserException Cela semble correct, merci. Je comprends la façon dont cela fonctionne, mais j'avais des problèmes avec eux. Y a-t-il un processus que vous avez utilisé pour aider à trouver vos réponses? –

Édition: Undeleted re: les commentaires dans la réponse de NullUserException.

1) Je pense personnellement que celui-ci est plus facile à conceptualiser si vous construisez d'abord un DFA qui peut accepter les chaînes. Je ne l'ai pas écrit, mais je pense que vous pouvez le faire avec 4 états et un état d'acceptation. De là, vous pouvez créer une expression rationnelle équivalente en supprimant les états un à la fois en utilisant un algorithme tel que this one. Cela est possible car les DFA et les expressions rationnelles sont prouvés équivalents.

2) Considérer le fait que l'étoile de Kleene ne s'applique qu'à l'expression régulière la plus proche. Par conséquent, si vous avez deux atomes individuels non groupés (un atome lui-même est une regex!), Il ne s'applique qu'à la seconde (comme, ab* correspondrait à un seul et un nombre quelconque - y compris 0 - b). Vous pouvez utiliser cela à votre avantage dans le cas où vous voulez que quelque chose existe, mais vous n'êtes pas sûr de combien il y en a.

Source

2010-10-05 21:59:27 eldarerathis

Prouver qu'une langue est régulière en donnant une expression régulière

Répondre

Questions connexes