lenguaajes automatasOnline version 2 paarcial by Johan Azael 1 Las expresiones regulares sobre un conjunto I son definidas recursivamente si estan vacias a ◮ El s´ımbolo ∅ (conjunto vac´ıo) b El s´ımbolo λ (conjunto {λ}) es una expresion regular c ◮ El s´ımbolo x (conjunto {x}) es una expresion regular ´ siempre que x ∈ I d ◮ Los s´ımbolos (AB), (A ∪ B), y A ∗ son expresiones regulares siempre que A y B son expresiones regulares e Los conjuntos representados por expresiones regulares son llamados conjuntos regulares. 2 Los conjuntos representados por expresiones regulares son llamados conjuntos regulares. Escoge una o varias respuestas a 10∗ b (1 ∪ 01)(10) ∗ c 0 ∪ 01 d 0(0 ∪ 1) ∗ e 10∗ f (1 ∪ 01)(10) ∗ 3 Teorema de Kleene Escoge una o varias respuestas a Un conjunto es regular si y solo si es reconocido por un automata de estado finito. b Automatas que reconocen conjuntos regulares 4 Automatas que reconocen conjuntos regulares a Automatas que reconocen los conjuntos ´ ∅, {λ} y {a} respectivamente b Transiciones: si λ ∈ A cada transicion que parta de ´ SB y desde cada estado previo a uno en FA ir hasta sB 5 Automatas que reconocen conjuntos regulares Escoge una o varias respuestas a Transiciones: por cada transicion desde ´ sA a un estado s para la entrada i, incluir transicion desde ´ {sA∗ } hasta s con el s´ımbolo i y una transicion desde cada estado final hasta ´ s para el mismo dato de entrada b S ∗ A = SA S {sA∗ } c Transiciones: por cada transicion desde ´ sA a un estado s para la entrada i, incluir transicion desde ´ {sA∗ } hasta s con el s´ımbolo i y una transicion desde cada estado final hasta ´ s para el mismo dato de entrada d S ∗ A = SA S {sA∗ }
New game