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 ciência-da-computação, é 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:
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 0
s a esquerda de todos os 1
s, 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 0
s nessa string? Bem, como x.y
tem exatamente p
0
s, isso significa que x.y.y.z
terá p + m
0
s, porém a quantidade de 1
s 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 0
s (palavras z
) ou com 1
s (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 a
s. 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.