5

Lendo uma questão sobre conceitos básicos de programação, deparo-me com a seguinte afirmação:

Sejam A e B duas linguagens sobre o alfabeto binário, isto é, sobre o alfabeto composto apenas por 0’s e 1’s. Seja A a linguagem na qual a quantidade de 0’s e 1’s é igual. Seja B a linguagem onde nenhum 0 ocorre após um caractere 1, apenas B é uma linguagem regular.

Procurando aqui no site encontro a resposta: O que é uma linguagem livre de contexto? porém, mesmo assim, não ficou claro.

Minhas perguntas:

  1. Quais são as principais diferença de uma linguagem regular para uma linguagem irregular? Na afirmação acima por que somente a linguagem B é regular?
  2. Quais o principais exemplos das duas linguagens?
11
  • 2
    Se sabes inglês, talvez isso te ajude 21/01/2019 às 19:39
  • 1
    Basicamente as linguagens irregulares são as não regulares, ou seja não existe um forma especifica, aliais o Victor citou várias, e linguagem regular ali se referia são as que podem ser expressadas com expressões regulares (tag: regex). Creio que se perdeu em algum momento no texto, que é bem extenso e informativo, mas realmente irregular não é "especifico". Aliais o termo irregular nem foi usado nas respostas, já que citam apenas regular e "outras". Não sou entendido do assunto, mas foi o que entendi em uma breve leitura.
    – Reptile
    21/01/2019 às 19:42
  • 1
    Creio que não, a propria regex dentro de uma linguagem de programação na verdade usa um interpretador, então algo como em PHP que use preg_match ou preg_replace, usa um sub-interpretador, ou seja expressão regular é a tal "linguagem regular", o PHP no caso só pega o resultado disto, como se fosse uma API interna, o mesmo é semelhante em outras linguagens.
    – Reptile
    21/01/2019 às 19:45
  • 1
    Me ajudou a esclarecer, pois estava com esse conceito em mente, muito obrigado @GuilhermeNascimento 21/01/2019 às 19:51
  • 2
    Vou responder assim que der, mas, antes, só evitar um engano comum: as expressões regulares modernas (com retrovisores e tal) não representam apenas as linguagens regulares, mas um superconjunto que engloba inclusive algumas linguagens sensíveis ao contexto (mais amplas que as livres de contexto já citadas na questão linkada). 21/01/2019 às 23:21

1 Resposta 1

4

Bem, acho que a resposta aqui talvez não agrade muito, mas é a correta: uma linguagem regular é aquela que pode ser gerada por uma gramática regular.

E, daí, o que seria uma gramática regular? Bem, seria uma gramática que possua apenas produções regulares. Bem, isso eu já expliquei nesta resposta.

Reiterando o que foi falado na resposta acima: uma linguagem regular é intimamente relacionada a uma cadeia de Markov, onde para cada linguagem regular, há uma cadeia de Markov que a representa em forma e conteúdo.


Sobre gramática irregular... bem, estamos lidando aqui com um problema semântico. Estou tomando esse prefixo i- como sendo a negação do radical que se segue, no caso seria o regular. Nesse sentido, você teria as linguagens "não-regulares". O que significa qualquer linguagem que não possa ser descrita através de uma linguagem regular.

Porém, voltemos um passo. Qual a definição de número irracional? Seriam os números complementares aos racionais (isto é, os não-racionais)? Pois bem, a raiz quadrada de 2 e até mesmo o pi não são números racionais, daí posso chamá-los de irracionais, confere? Bem, até aí tranquilo, mas e quanto a raiz quarta de -1? Seria esse número irracional? Sabemos que não, esse número é um número complexo, e o número complexo não é nem racional nem irracional. Então, a definição de número irracional não pode ser simplesmente "aquele número que não é racional", ainda mais definindo os números reais como sendo a união dos racionais com os irracionais.


A linguagem não ser regular significa que não tem forma específica? Bem, na verdade verdade, não. Ela pode ter uma forma extremamente específica.

Por exemplo, a linguagem D formada por uma palavra de um alfabeto binário seguida dela mesma? Essa linguagem é definida mais ou menos assim: D = { WW, para todo W em {a,b}* }. Essa linguagem tem uma forma bem específica, porém é não regular (vou provar isso aqui depois de provar as linguagens A e B).


Sobre expressões regulares e linguagens regulares. No início, regex representavam sim linguagens regulares. Mas começaram a acrescentar coisas que não são regulares. Por exemplo, botaram a possibilidade de ter um retrovisor na consulta da regex. Em alguns motores de busca, eu posso reconhecer exatamente D:

([ab]*)\1

Também tem as opções de look-ahead e negative look-ahead para fazer um melhor caminho na máquina de estados e reconhecer/negar uma palavra. Porém, esse "olhar adiante" significa que não estamos mais lidando com uma cadeia de Markov. Ou seja, não regular. O look-behind significa a existência de memória, o que significa, novamente, não ser uma cadeia de Markov.

Você pode ver mais sobre regex vs linguagens regulares nesta pergunta, nos seus comentários e na resposta aceita.


O @anonimo comentou sobre a Hierarquia de Chomsky. Porém, ele colocou no nível 0 tanto as linguagens recursivas quanto as linguagens recursivamente enumeráveis. Mas isso tem encrencas.

Um problema de decisão, na , é equivalente a reconhecer se a entrada pertence à determinada linguagem, e quem define qual a linguagem válida é o problema. Por exemplo, o Problema da Parada é tão equivalente a verificar se, por acaso, uma palavra pertence a uma gramática irrestrita; esse é um problema da classe RE.

Porém, posso definir, em cima de uma linguagem qualquer, a sua linguagem complemento. Por exemplo, o Problema da Trava (que é a negação do Problema da Parada, que deve responder sim se o programa travar). Ele é o complemento do Problema da Parada. Ele é considerado um problema da classe co-RE. Ou seja, o Problema da Trava é equivalente a detectar se uma palavra pertence a uma linguagem co-RE.

Eu entro em mais detalhes dessas classe de complexidade na resposta sobre busca em largura vs busca em profundidade.


Já respondi qual a diferença de uma linguagem regular para as outras. Todo o resto é consequência disso.

Uma dessas consequências é que as linguagens regulares obedecem ao lema do bombeamento. Podem existir linguagens não regulares que também obedeçam a esse lema, mas a não obediência implica necessariamente em ser não regular.

Leia mais nesta resposta.

Leia mais (em inglês)

Então, como usar para provar que A não é regular?

Considere o operador . como o operador de concatenação de palavras (recebe como operando duas palavras, retorna sua concatenação; "abc" . "def" == "abcdef"), e o operador ^ como o de repetição de palavras (recebe uma palavra e um número natural e retorna aquela palavra repetida o número vezes; ""ba"."na"^3 == "ba"."nanana" == "bananana"; "ba"."na"^0 = "ba").

Precisamos, para tal, achar uma palavra no formato x.y.z pertencente a A e um número p tal que:

  • |y| >= 1
  • |x.y| <= p

De modo que, ao bombear y algumas vezes, a nova palavra x.y^n.z não pertença mais a A.

Então, peguemos a palavra formada por todos os 0s a esquerda de todos os 1s, e ambos com a mesma quantidade. Como p é arbitrário, então podemos pegar a palavra "0"^p . "1"^p. O que isso implica? Como |x.y| <= p, não é possível que y possua o caracter 1. Ou seja, y = "0"^m, 1 <= m <= p.

Bombeemos, então, y uma vez adicional. Ou seja, de x.y.z obteremos x.y^2.z, que é idêntico a x.y.y.z. Então, e a quantidade de 0s nessa string? Bem, como x.y tem exatamente p 0s, isso significa que x.y.y.z terá p + m 0s, porém a quantidade de 1s não é alterada. Ou seja, se x.y.y.z pertencer a A, isso implica necessariamente em p + m = p; porém, sabemos que 0 < 1 <= m <= p, o que significa que p < 1 + p <= m + p <= 2*p. Portanto, p < p + m. Logo, x.y.y.z não pertence a A. Logo, A não é regular pois não atende ao lema do bombeamento.


Para provar que B é regular, basta escrever uma regex (regex pura, sem look-arounds, retrovisores ou outra coisa que não seja regular). Basicamente, nos resta as listas, listas negadas, agrupamentos, escolha (indicado normalmente pela barra-vertical |), quantificadores (opcional, estrela de Kleene, cruz de Kleene).

Em B, nenhum 0 pode ser precedido por 1. Ou seja, se tiver a subpalavra 10, já não pertence a B. Isso significa que palavras apenas com 0s (palavras z) ou com 1s (palavras u) são válidas. Além disso, posso fazer uma nova palavra com z.u sem nenhum problema.

Quem é o conjunto das palavras z? É 0*. E o conjunto das palavras u? É 1*. Portanto, z.u é a expressão regular 0*1*.

Ou seja, B pode ser escrita como 0*|1*|0*1*. Porém isso é trivialmente simplificado para 0*1*. Como temos uma expressão regular, B é uma linguagem regular.

Sua gramática:

S -> '0'.S
S -> '0'
S ->
S -> '1'.U
U -> '1'.U
U -> '1'

Seu autômato de estados finito (com transação lambda, considerando que todos os estados são estados de aceitação):

 +---+       +---+
>| q0|>--+-->| q1|>--+
 +---+   |   +---+   |
   ^     |     ^     |
   |     |     |     |
   +- 0 -+     +- 1 -+

Vamos provar que D não é regular? Ela é a linguagem da palavra binária duplicada.

Escolhemos a palavra "a"^p . "b"^p . "a"^p . "b"^p. Ela é exatamente a palavra "a"^p . "b"^p duas vezes, portanto pertence a D. Isso significa que, necessariamente, y será composto puramente por as. E daí? E daí que, bombear y significa obter a seguinte palavra:

"a"^n . ("a"^p . "b"^p)^2

Portanto, essa nova palavra não é uma duplicação de palavra. Logo, não pertence a D. Logo, D não é regular.

2
  • Jefferson, hoje estou viajando, mas amanha irei ler com máxima atenção sua resposta, mas desde já muito obrigado mesmo!! 24/01/2019 às 16:45
  • Sensacional sua resposta!!! Consegui compreender muito bem quando você provou que A não é regular, mas B sim! Apenas deu um pequeno nó no cérebro quando você mencionou 'look-ahead e negative look-ahead ', mas procurei aqui no site e já consegui sanar as dúvidas!Muito obrigado mesmo @Jefferson 25/01/2019 às 18:31

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 .