Definindo gramática para a linguagem dada

Question

Estou tentando praticar para um exame e estou tendo algum problema em um dos problemas práticos. O problema pede para identificar uma variedade de linguagem como gramática regular, gramática sem contexto, gramática de sensibilização de contexto ou gramática irrestrita. Também pergunta que se a gramática é regular ou sem contexto, para escrever a gramática exata. Eu não estou tendo problemas com dois dos 4 pedaços de linguagem. Por exemplo, o mais fácil é o seguinte:

$ \ {a ^ n $ onde $ n \ GE0 $ , $ n \ pmod 3 \n\ \ Not= 1 \} $ pode ser descrito pela gramática regular $ a \ rightarrow AA \ Mid A $

No entanto, a linguagem que estou lutando é:

$$ \ {a ^ n b ^ m \ text {onde} n> 1, m \ ge1, n> m \} $$

e

$$ \ {A ^ {2N} b ^ {3N} \ text {where} n \ ge1 \} $$

Eu acredito que a primeira língua é livre de contexto porque eu sei que a linguagem $ a ^ nb ^ n $ é livre de contexto de exemplos anteriores e pode ser descrito pela gramática $ a \ rightarrow AAB \ MED AB $ , no entanto, nesta versão, $ B $ é levado para a $ m $ potência em vez da $ n $ e os limites para $ m $ e $ n $ são diferentes, e não tenho certeza de como isso afeta a gramática que o descreve. Francamente, não tenho certeza de onde começar com a última parte da linguagem ... Eu não sei como determinar que tipo de gramática descreve, muito menos a própria gramática se estiver livre de contexto ou regular. .

Alguém poderia ajudar, ou pelo menos me apontar na direção certa?

Answer 1

Ambos os seus idiomas são livres de contexto e não regular. O primeiro pode ser gerado usando a seguinte gramática: $$ S \ para A S \ Mid A S B \ Mid Aab $$ O segundo pode ser gerado usando a seguinte gramática: $$ S \ to AASBBB \ MID AABBB $$

Você pode mostrar que esses idiomas não são regulares usando o lema de bombeamento ou usando a teoria do myhill-nerode. Deixe-me indicar brevemente como fazer o uso do lema de bombeamento.

Para a primeira língua, suponha que fosse regular. Deixe $ P $ ser a constante prometida pelo lema de bombeamento. Em seguida, a palavra $ a ^ {p + 1} b ^ p $ está no seu idioma. De acordo com o lema, ele pode ser escrito como $ xyz $ , onde $ | xy | \ leq p $ consiste unicamente de $ a $ 's, e $ y \ neq \ epsilon $ < / span>. Mas então $ xy ^ 0z $ não está no seu idioma.

A segunda língua é ainda mais simples e deixada para você.