Uma expressão regular pode ser infinita?

Eu sei que idiomas que podem ser definidos usando expressões regulares e reconhecíveis pelo DFA / NFA (autômatos finitos) são equivalentes. Também não existe DFA para o idioma . Mas ainda assim ele pode ser escrito usando expressões regulares (para que o assunto qualquer linguagem não-regular pode ser) como . Mas sabemos que toda linguagem que tem uma expressão regular tem um DFA que a reconhece (contradição com minha afirmação anterior). Sei que isso é trivial, mas a definição de expressão regular inclui a condição de que ela deve ser finita? $\{0^n1^n|n \ge 0\}$ $\{ \epsilon \} \cup \{01\} \cup \{0011\}......$

formal-languages regular-languages regular-expressions sashas
fonte

Você já respondeu à sua própria pergunta: se REG

⊊

$\subsetneq$ CFL, esses termos não podem ser expressões regulares.

Raphael

Apenas uma nota lateral: se deixar cair a exigência de DFA / NFA serem finitos, nós podemos construir um autômato para aceitar

{0^{n} 1^{n} ∣ n \geq 0}

$\{0^n1^n\mid n\geq0\}$ .

Como ponto de terminologia, a palavra 'autômato' é o plural de 'autômato'. Não há palavra 'autômatos' - você não pode torná-lo mais plural do que já é. (autômatos estão corretos como possessivos, mas não como plurais)

chasly de UK

Respostas:

Se fosse permitido que expressões regulares fossem infinitas, qualquer idioma teria sido regular.

Dada a linguagem , sempre podemos definir a expressão regular , que define exatamente . (Exemplo: a expressão regular define .) $L=\{w_1, w_2, \ldots\}$ $R = w_1 + w_2 + \cdots$ $L$
$R_1 = \epsilon+0+1+00+01+10+11+\cdots$ $L_1=\{0,1\}^*$

Sabemos que algumas línguas não são regulares, portanto, isso mostra que expressões regulares infinitas descrevem uma classe maior de línguas do que expressões regulares finitas.

Tocou.
fonte

Adoro essa resposta, porque ela diz não apenas que infinitas expressões regulares são diferentes, mas que o conceito como um todo não é significativo.

Jmite #

Uma declaração mais sucinta do ponto que eu enterrei no meu segundo parágrafo e, portanto, mais clara.

Davislor

Mas conclui com uma tautologia pura. Por que não consideramos todos os idiomas regulares, então, se eles têm esse formulário? As coisas que fazemos com expressões regulares não funcionam mais. Não podemos construir uma máquina de estados por um algoritmo indutivo, porque nunca termina e possui estados infinitos. Não podemos comparar com tudo na lista e rejeitar se nada corresponder. E não podemos representar fisicamente a lista de qualquer maneira. (As listas que podemos gerar por computador são os idiomas decidíveis.) Podemos provar coisas usando o fato de que todas as línguas têm esse formato, mas não o tipo de coisa que sabemos sobre regexes.

Davislor

@jmite "não tem sentido" ou um caso especial?

BAR

@BAR Não é significativo, pois na classe de idiomas sobre descrita por infinitas expressões regulares é apenas ou seja, o conjunto de todos os idiomas. Não temos uma classe de idiomas da mesma maneira que você faz com REs finitos, CFGs ou mesmo Turing Machines.

Σ

$\Sigma$

2^{Σ}

$2^{\Sigma}$

Jmite #

Sim, deve ser finito. Imagine que você tem esse conjunto infinito de correspondências possíveis, e sua entrada é 011. Você seria capaz de rejeitá-lo? Você ficaria sem jogos para conferir?

Existe alguma linguagem que, por essa definição, não seja regular ? E o conjunto de todos os pares de programas e entradas, de modo que o programa especificado pare na entrada especificada?

Agora, se você tivesse um programa que enumerasse as strings em um idioma em ordem lexicográfica,

Atualizar

Para esclarecer um pouco com base no feedback dos comentários, a razão pela qual nem todos os idiomas deste formulário são regulares é por definição. Se, por exemplo, você procurar a prova do teorema de Kleene, isso depende do fato de que uma expressão regular deve ser finita para provar que gera uma máquina de estados finitos.

Por que definimos uma linguagem "regular" dessa maneira? Como toda linguagem formal é um subconjunto das strings de um alfabeto, e todo conjunto de strings pode ser expresso como uma união de singletons, portanto, se chamarmos qualquer conjunto de strings de um idioma "regular", o idioma regular seria apenas sinônimo de idioma . Essa não é uma definição muito útil, especialmente porque não podemos realmente implementá-la em hardware ou software. Não podemos armazenar uma lista infinita arbitrária em nenhum lugar ou construir uma máquina de estado infinito.

Como sugeri, no entanto, se você tiver uma maneira de enumerar todas as seqüências de caracteres em um idioma em ordem, poderá criar uma decisão a partir disso (aceite quando vir a sequência exata, rejeite quando encontrar uma sequência que vem depois da sequência que você está procurando) e vice-versa (para cada sequência em ordem, execute-a pelo decider e faça a saída se e somente se for aceita). Portanto, se considerássemos todos os idiomas enumeráveis regulares , todos os idiomas decidíveis seriam “regulares” e precisaríamos de um novo termo para os idiomas reconhecidos por máquinas de estados finitos e suas codificações equivalentes como expressões finitas.

Davislor
fonte

Esta resposta está errada. O fato de que alguma representação de uma linguagem não se presta a construir um decisor algorítmico de maneira ingênua não implica que essa representação esteja errada; poderia haver outras abordagens. De fato, toda linguagem decidível tem uma representação da forma que sasha propõe! Em suma, você está cometendo a falácia "Não consigo ver como, então isso deve ser impossível".

Raphael

@Raphael: Por favor, considere as implicações de sua afirmação: " toda linguagem decidível tem uma representação da forma que Sasha propõe!" Na verdade, esse é o argumento que eu estava afirmando na minha resposta. A questão era : todos os idiomas deste formulário são definidos como regulares? Bem, todo idioma decidível é regular? (E, como mostrei, alguns indecidíveis também?) Essa seria uma definição útil de "regular"?

Davislor

Além disso, longe de falhar que uma decisão para uma lista infinita de strings não pode ser feita, minha última frase foi uma dica de como isso poderia ser feito: se a lista de strings estiver bem ordenada, você poderá rejeitá-la assim que possível. conforme você encontra uma sequência na ordem. No entanto, uma máquina de estados finitos não pode fazer isso porque não pode representar todos os estados de comparação com cada cadeia de caracteres na lista infinita, nem expressões regulares. Se pudessem, seriam poderosos o suficiente para reconhecer todos os idiomas decidíveis.

Davislor

Suponha que expressões regulares pudessem ser infinitas.

Assim, o idioma definido por {ϵ} ∪ {01} ∪ {0011} ... será regular. Para cada idioma regular existe um NFA. Uma maneira de obter esse NFA seria ter NFAs individuais para cada um dos {ϵ}, {01}, {0011} ... e combiná-los usando as transições ϵ. Como existem infinitas expressões regulares distintas, precisaremos combinar sub-NFAs infinitos. No entanto, a NFA pode ter apenas um número finito de estados (definição de NFA).

Portanto, não existe NFA que possa definir a linguagem definida pela união de infinitas expressões regulares, o que implica que a linguagem não é regular.

Portanto, não há expressão regular que possa definir o mesmo idioma que o idioma definido pela união de infinitas expressões regulares.

Assim, expressões regulares podem ter apenas expressões finitas.

Anurag Peshne
fonte

Suas "expressões regulares infinitas" definem outra classe de idiomas, não os idiomas regulares. De fato, eles são capazes de definir qualquer idioma, e isso é totalmente desinteressante (eles não são finitos, são difíceis de trabalhar; e podem fazer qualquer coisa, portanto nada para estudar em termos de limitações).

vonbrand