Deixe um número ser dado. Considere o seguinte idioma L n = {nnn .eun= {w w|w ∈ { 0 , 1 }n}Ln={ww|w∈{0,1}n}L_n = \{ \; ww \; \vert \; w \in \{0,1\}^{n} \; \} Em palavras, é o conjunto de cadeias de cópia de comprimento 2 n .eunLnL_n2 n2n2n Considere a seguinte função de complexidade de estado...
Onde posso encontrar uma introdução aos autômatos probabilísticos e o que eles reconhecem (certas funções de palavras a )? Existe um termo padrão para essas funções que são reconhecidas por autômatos probabilísticos, análogos a "linguagens regulares" para o que os autômatos finitos determinísticos...
P⊆CSLP⊆CSLP\subseteq CSLP⊈CSLP⊈CSLP\not\subseteq CSL PPP é o conjunto de todos os idiomas decidíveis em tempo polinomial em uma máquina de Turing determinística, e CSLCSLCSL é a classe de linguagens sensíveis ao contexto, conhecida por ser equivalente a , as linguagens decididas por autômatos com...
É simples ver que os poderes de 2 sobre o alfabeto {0,1} são regulares porque é uma expressão regular para ele.10∗10∗10^* Mas os poderes de 2 representados no ternário parecem não ser regulares. É difícil aplicar classes de lema ou resíduo de bombeamento, pois parece haver muito pouco padrão entre...
Na minha experiência, linguagens sensíveis ao contexto e autômatos limitados lineares são freqüentemente ignorados ou ignorados nos cursos de teoria da computabilidade e são deixados de fora de alguns livros de texto notáveis, embora os autômatos finitos e pushdown recebam muita atenção. Certamente...
Existem permutações e tamanho polinomial (em | w | = n ) gramática livre de contexto que descreve a linguagem finita { w π 1 ( w ) π 2 ( w ) } sobre o alfabeto { 0 , 1 } ?π1,π2π1,π2\pi_1,\pi_2|w|=n|w|=n|w|=n{wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\}{ 0 , 1 }{0,1}\{0,1\} ATUALIZAÇÃO: Para...
Os analisadores de gráficos podem ser implementados com base na forma normal de Chomsky ou diretamente com base nas regras de produção. Vamos, por enquanto, supor que temos um analisador de gráfico CYK que usa a forma normal de Chomsky. A binarização não está definida exclusivamente. Isso afeta o...
Eu queria saber sobre quais conjuntos de idiomas são gerados por restrições de expressões regulares. Supondo que todas as restrições tenham um símbolo constante para cada elemento de e concatenação. Então, oito classes podem ser formadas pela presença ou ausência de complemento / negação, alteração...
Estou aprendendo a teoria algébrica da análise. Meu primeiro problema é identificar exemplos de semicondutores específicos da teoria formal da linguagem. Aqui está uma tentativa de construir dois exemplos. 1 Dada a gramática CNF, os elementos de semiring são conjuntos de símbolos terminais e não...
Gostaria de saber por que, para o reconhecimento de linguagens sem contexto, apenas os autômatos não determinísticos de push-down (DPA = NPDA) funcionam. Por que os autômatos push-down determinísticos (DPDA) não reconhecem esses
Se existem resultados na resolução de problemas de linguagens formais usando análise matemática, matemática contínua. Por exemplo, resolvendo o problema de não vazio de interseção para uma linguagem livre de contexto e uma linguagem
Qual é a proporção de CFGs ambíguos para todos os CFGs ? Como os dois conjuntos são infinitamente contáveis, a proporção não está bem definida. Mas e a densidade assintótica : limn ↦ ∞# ambiguous CFG of size<n# CFG of size<nlimn↦∞# ambiguous CFG of size<n# CFG of size<n\lim_{n \mapsto...
Seja um alfabeto finito. Para um determinado idioma L ⊆ A * o monoid sintática M ( L ) é uma noção bem conhecida na teoria da linguagem formal. Além disso, um monóide M reconhece uma linguagem L se existir um morfismo φ : A ∗ → M tal que L = φ - 1 ( φ ( L ) ) ) .AAAL⊆A∗L⊆A∗L \subseteq A^{\ast}...
Existem vários modelos diferentes para definir transformações entre idiomas. Transdutores de estado finito e transformações de gráficos definíveis pelo MSO sobre gráficos de cadeias de caracteres são as duas com as quais estou melhor familiarizado. Sabemos que os transdutores de estado finito...
Sabemos que todos os autômatos push-down são representáveis usando gramáticas sem contexto. Além disso, existe um algoritmo para construir um CFG a partir de qualquer PDA (por exemplo, a prova de Sipser na introdução à teoria da computação). Existem ferramentas que fazem essa tradução? Ou seja,...
Para uma dada linguagem livre de contexto G, chamamos um não-terminal anulável se , ou seja, podemos derivar a string vazia de depois de aplicar um número finito de produções.UMAEuUMAEuA_i UMAEu→∗ϵUMAEu→∗ϵA_i \rightarrow^* \epsilonUMAEuUMAEuA_i Existe um algoritmo simples para determinar quais...
Escreva como o mapa de Parikh --ie, , onde é o número de vezes que aparece em . É sabido que, para um CFL , é um conjunto semilinear (esse é o teorema de Parikh). Outras coisas interessantes são conhecidas, mas não encontrei nada sobre o mapa de Parikh de uma linguagem sensível ao contexto. Em...
Considere uma linguagem regex com o quantificador ganancioso , o quantificador não-viciado, alternância ordenada e classes de caracteres. (Essa é essencialmente uma sub-linguagem do PCRE, sem referências anteriores, afirmações gerais ou alguns dos outros bits mais sofisticados.)∗ ?∗∗*∗?∗?{*}? Uma...
Estou tentando esclarecer meu entendimento no exemplo apresentado na Seção 2.2 dos autômatos finitos quânticos de 1 via: fortalece as fraquezas e as generalizações (esse link alternativo também pode ser útil). Este exemplo fornece um exemplo muito simplificado de um 1-QFA com as seguintes regras de...
No meu trabalho surgiu o problema da classificação CFL em imagens de funções racionais. Em outros termos, o que classe de linguagens formar línguas , para contexto fixo linguagem livre e transdutor de estados finitos determinística . Obtive alguns resultados fáceis, como a linguagem Dyck com duas...