4

Conforme consta no título, segue a DFA que aceita a linguagem proposta:

inserir a descrição da imagem aqui

A minha dúvida é com relação a expressão regular dessa DFA que é a seguinte:(1*01*01*)*. Conforma a expressão regular, não significa que qualquer string que venha dali comece com o binário 1?

1
  • A expressão regular correta para essa imagem não seria 1*(01*01*)*? Na imagem o automato aceita tanto a palavra vazia quanto palavras com vários 1.
    – ArturB
    Commented 1/09/2023 às 17:42

1 Resposta 1

4

Não, a string não precisa necessariamente começar com 1.

Afinal, 1* quer dizer "zero ou mais ocorrências de 1". O quantificador * admite zero ocorrências, o que quer dizer que o 1 não é obrigatório (veja alguns exemplos).

Só um detalhe: a regex possui um quantificador em volta dos parênteses: (...)*, o que quer dizer que tudo que está entre os parênteses também pode ocorrer zero vezes. Ou seja, a regex também aceita strings vazias (ou "nada" - veja aqui como ela encontra um match).

Se bem que zero é um número par, então "zero ocorrências" do dígito 0 também é um "número par de zeros" (mas se a string não for vazia, aí deve ter pelo menos dois zeros).


Se não quiser considerar válida uma string vazia, pode trocar a regex para (1*01*01*)+, pois o quantificador + significa "uma ou mais ocorrências", ou seja, o que está entre parênteses deve ocorrer pelo menos uma vez. Assim, a string vazia não é mais considerada válida.

7
  • Muito obrigado pela resposta, ficou claro. Porém agora notei outra coisa que me deixou em dúvida. No caso a string contendo apenas um par de zeros 00 seria aceita? Ou obrigatoriamente ela terá 0101
    – Pirategull
    Commented 29/10/2019 às 20:04
  • 1
    @Pirategull Um par de zeros aceita sim: regex101.com/r/lwuDlv/4 - repare que todos os 1 tem um * logo depois, então todos podem ocorrer zero ou mais vezes.
    – hkotsubo
    Commented 29/10/2019 às 20:05
  • Puxa, que legal o link que você enviou, não conhecia me será muito útil obrigado. Mas ainda não consigo entender muito bem como funciona essas expressões. (Edit: agora entendi, eu tava considerando como se fosse (01)*. Desculpe
    – Pirategull
    Commented 29/10/2019 às 20:08
  • 1
    @Pirategull Expressões regulares é um assunto bem complexo. Eu sugiro começar por aqui e depois aqui
    – hkotsubo
    Commented 29/10/2019 às 20:10
  • 1
    @Pirategull Se quer o próprio caractere sigma (Σ), é só colocá-lo. Se quer dizer que pode ter um 0 ou 1, pode usar [01]: regex101.com/r/WuqtcJ/1
    – hkotsubo
    Commented 29/10/2019 às 20:15

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .