Linguagem algébrica

Na teoria da linguagem formal , uma linguagem algébrica ou linguagem não contextual é uma linguagem gerada por uma gramática algébrica . De maneira equivalente, uma linguagem algébrica é uma linguagem reconhecida por um autômato push-down .

As linguagens algébricas formam as linguagens do tipo 2 na hierarquia de Chomsky . Eles têm aplicações importantes na descrição de linguagens de programação e em linguística . Eles também estão envolvidos na descrição de linguagens XML .

Existem vários termos para uma linguagem algébrica: às vezes há linguagem "  livre de contexto  " , ou linguagem não contextual , linguagem livre de contexto , linguagem contextual  ; todos esses termos são usados ​​e equivalentes.

Alguns exemplos

As linguagens algébricas visam capturar uma estrutura de palavras que consiste em associações de símbolos, normalmente representados por grupos de parênteses; essas palavras e linguagens correspondem bem a expressões estruturadas em linguagens de programação (a estrutura início - fim ou indentação) e também são representadas na hierarquia de informações por árvores, por exemplo. Todas essas possibilidades estão além das capacidades da linguagem racional .

• Língua {nonãobnão∣não⩾0}={ε,nob,nonobb,nononobbb,...}{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geqslant 0 \} = \ {\ varepsilon, ab, aabb, aaabbb, \ dots \}}é o exemplo típico de uma linguagem algébrica que não é uma linguagem racional . É composto de palavras que têm tantas letras quantas são as letras , e com a condição adicional de que as letras precedam as letras .no{\ displaystyle a}b{\ displaystyle b}no{\ displaystyle a}b{\ displaystyle b}
• As linguagens Dyck (são linguagens bem palavras entre parênteses) são linguagens algébricas.

• Expressões aritméticas, usando as quatro operações elementares, por exemplo , etc., formam uma linguagem algébrica. Além disso, é essa observação que historicamente é a base do desenvolvimento de compiladores que devem, entre outras coisas, traduzir expressões aritméticas complexas, decompondo-as em operações elementares.no×b+(no+b)/d{\ displaystyle a \ times b + (a + b) / d}

Para provar que uma linguagem é algébrica, fornecemos uma gramática não contextual que a gera. Veja o parágrafo de exemplos do artigo em questão para mais detalhes. Para linguagens mais complicadas, podemos usar métodos mais poderosos, como transduções racionais ou o fato de que as linguagens algébricas formam uma família abstrata de linguagens .

• Língua {nonãovsm1dm1vsm2dm2⋯vsmnãodmnão∣não,m1,...,mnão≥1}{\ displaystyle \ displaystyle \ {a ^ {n} c ^ {m_ {1}} d ^ {m_ {1}} c ^ {m_ {2}} d ^ {m_ {2}} \ cdots c ^ {m_ {n}} d ^ {m_ {n}} \ mid n, m_ {1}, \ ldots, m_ {n} \ geq 1 \}} é algébrico. As palavras desta língua são compostas por um primeiro grupo formado por um certo número de letras , seguido de tantos blocos; cada um desses blocos é composto de letras seguidas do mesmo número de . Esta descrição dá uma indicação de como construir a linguagem: é obtida a partir da linguagem , substituindo cada letra , linguagem . Como as linguagens algébricas são fechadas por substituição (veja abaixo), a linguagem resultante é algébrica.no{\ displaystyle a}vs{\ displaystyle c}d{\ displaystyle d}{nonãobnão∣não≥1}{\ displaystyle \ {a ^ {n} b ^ {n} \ mid n \ geq 1 \}}b{\ displaystyle b}{vsmdm∣m≥1}{\ displaystyle \ {c ^ {m} d ^ {m} \ mid m \ geq 1 \}}

• A linguagem Goldstine de duas letras , é ainda mais complicada. É o conjunto de palavrasG{\ displaystyle G}no{\ displaystyle a}b{\ displaystyle b}nonão1bnonão2b⋯nonãopb{\ displaystyle \ displaystyle a ^ {n_ {1}} ba ^ {n_ {2}} b \ cdots a ^ {n_ {p}} b}onde , e para um com . Então, nós queremos que ou ou ... . É quase mais fácil perguntar quando uma palavra n ' não está na língua: é quando todos iguais , então quando a palavra está . Para verificar se esta linguagem é algébrica, partimos da linguagem algébrica p≥1{\ displaystyle p \ geq 1}nãoeu≥0{\ displaystyle n_ {i} \ geq 0}nãoj≠j{\ displaystyle n_ {j} \ neq j}j{\ displaystyle j}1≤j≤p{\ displaystyle 1 \ leq j \ leq p}não1≠1{\ displaystyle n_ {1} \ neq 1}não2≠2{\ displaystyle n_ {2} \ neq 2}nãop≠p{\ displaystyle n_ {p} \ neq p}nonão1bnonão2b⋯nonãopb{\ displaystyle a ^ {n_ {1}} ba ^ {n_ {2}} b \ cdots a ^ {n_ {p}} b}nãoj{\ displaystyle n_ {j}}j{\ displaystyle j}nobno2b⋯nopb{\ displaystyle aba ^ {2} b \ cdots a ^ {p} b}
  {nopbqvs∣p,q≥0,q≠p+1}{\ displaystyle \ displaystyle \ {a ^ {p} b ^ {q} c \ mid p, q \ geq 0, q \ neq p + 1 \}} e aplicamos a substituição no↦no∗b,b↦no,vs↦b(no∗)b∗.{\ displaystyle \ displaystyle a \ mapsto a ^ {*} b, \ quad b \ mapsto a, \ quad c \ mapsto b (a ^ {*}) b ^ {*}.} A linguagem é o resultado desta substituição; esta linguagem está ligada à palavra infinitaG{\ displaystyle G}x=nobno2bno3b⋯nonãob⋯{\ displaystyle \ displaystyle x = aba ^ {2} ba ^ {3} b \ cdots a ^ {n} b \ cdots}.Com efeito, a língua é o conjunto de palavras que não são prefixos de palavras de e que terminam com a letra .G{\ displaystyle G}x{\ displaystyle x}b{\ displaystyle b}

Propriedades

Toda linguagem racional é algébrica porque pode ser descrita por uma gramática regular , que é um caso especial de gramática não contextual.

Propriedades da cerca

A classe de linguagens algébricas tem certas propriedades de fechamento  :

• a união e a concatenação de duas linguagens algébricas são linguagens algébricas;
• a estrela de uma linguagem algébrica é algébrica;
• a interseção de duas linguagens algébricas não é necessariamente assim. Por exemplo, a interseção de linguagens e é . Esta linguagem não é algébrica (nós a provamos tradicionalmente usando um lema de iteração para linguagens algébricas ). Conseqüentemente, a classe das linguagens algébricas também não é fechada por complementares  ;{nonãobnãovsm∣não,m>0}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} \ mid n, m> 0 \}}{nonãobmvsm∣não,m>0}{\ displaystyle \ {a ^ {n} b ^ {m} c ^ {m} \ mid n, m> 0 \}}{nonãobnãovsnão∣não>0}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {n} \ mid n> 0 \}}
• a imagem espelhada de uma linguagem algébrica é uma linguagem algébrica;
• a interseção de uma linguagem algébrica e uma linguagem racional é sempre algébrica;
• a imagem homomórfica, a imagem homomórfica inversa de uma linguagem algébrica é algébrica.

A partir dessas propriedades, segue-se que:

• as linguagens algébricas são fechadas por transdução racional , portanto formam um cone racional;
• linguagens algébricas são fechadas para operações racionais (união, produto, estrela), portanto, formam uma família abstrata de linguagens .

Encerramento por substituição

Uma substituição de in é uma aplicação de no conjunto das partes do qual é um morfismo de monoides, ou seja, satisfaz ambas as propriedades: NO∗{\ displaystyle A ^ {*}}B∗{\ displaystyle B ^ {*}}σ{\ displaystyle \ sigma}NO∗{\ displaystyle A ^ {*}}B∗{\ displaystyle B ^ {*}}

1. σ(ε)={ε}{\ displaystyle \ sigma (\ varepsilon) = \ {\ varepsilon \}} ;
2. σ(xy)=σ(x)σ(y){\ displaystyle \ sigma (xy) = \ sigma (x) \ sigma (y)}para palavras e .x{\ displaystyle x}y{\ displaystyle y}

Na segunda fórmula, o produto é o produto das partes de . B∗{\ displaystyle B ^ {*}}

Uma substituição é algébrica se for uma linguagem algébrica para qualquer letra . σ{\ displaystyle \ sigma}σ(no){\ displaystyle \ sigma (a)}no{\ displaystyle a}

O teorema da substituição afirma que se é uma substituição algébrica, então é uma linguagem algébrica para qualquer linguagem algébrica . σ{\ displaystyle \ sigma}σ(eu){\ displaystyle \ sigma (L)}eu{\ displaystyle L}

Propriedades indecidíveis

A pertença de uma palavra a uma linguagem algébrica é decidível  ; ele pode ser testado usando o algoritmo CYK . Também sabemos como decidir se uma linguagem algébrica (definida a partir de uma gramática) está vazia.

Mas, ao contrário das linguagens racionais, muitos outros problemas com linguagens algébricas são indecidíveis. Por exemplo, não existe um algoritmo para decidir se duas línguas algébricas são iguais. Mais precisamente, as seguintes propriedades são indecidíveis. Vamos , , linguagens algébricas, dadas por exemplo, por sua gramática em um alfabeto , e é uma linguagem racional. São indecidíveis: eu{\ displaystyle L}eu1{\ displaystyle L_ {1}}eu2{\ displaystyle L_ {2}}NO{\ displaystyle A}R{\ displaystyle R}

• eu1∩eu2=∅{\ displaystyle L_ {1} \ cap L_ {2} = \ emptyset} ;
• eu=NO∗{\ displaystyle L = A ^ {*}} ;
• eu1=eu2{\ displaystyle L_ {1} = L_ {2}} ;
• eu1⊂eu2{\ displaystyle L_ {1} \ subconjunto L_ {2}} ;
• eu=R{\ displaystyle L = R} ;
• R⊂eu{\ displaystyle R \ subset L} ;
• O complemento de é algébrico;eu{\ displaystyle L}
• eu1∩eu2{\ displaystyle L_ {1} \ cap L_ {2}} é algébrico;
• eu{\ displaystyle L} é racional;
• eu{\ displaystyle L}é inerentemente ambíguo. É até indecidível que uma dada gramática não seja ambígua.

Linguagens algébricas determinísticas e inequívocas

Linguagens determinísticas

Uma linguagem algébrica é considerada determinística se for reconhecida por um autômato push-down determinístico .

A classe das linguagens algébricas determinísticas contém a classe das linguagens racionais e está estritamente incluída na das linguagens algébricas. O contra-exemplo típico de linguagem algébrica não determinística é o conjunto de palíndromos .

A definição implica que a pertença de uma palavra a uma linguagem algébrica determinística pode ser testada em tempo linear, ao contrário do caso de linguagens algébricas arbitrárias. Além disso, qualquer linguagem algébrica determinística pode ser descrita por uma gramática LR (1) e vice-versa. Isso permite que sejam usados ​​para aplicações práticas. Assim, a maioria das linguagens de programação são linguagens algébricas determinísticas.

A classe de linguagens algébricas determinísticas é fechada por complementares. Contudo:

• não é fechado por intersecção (mesmo contra-exemplo do caso não determinístico);
• não é fechado por união (conseqüência do fechamento por complementar e não fechamento por cruzamento);
• não é fechado por concatenação (a estrela de Kleene da linguagem definida acima é algébrica determinística, mas não );eu1∗{\ displaystyle L_ {1} ^ {*}}eu1{\ displaystyle L_ {1}}eu1∗.eu2{\ displaystyle L_ {1} ^ {*}. L_ {2}}
• não é fechado por espelho, por exemplo, é algébrico determinístico, mas não .{vsnonãobnão}∪{dno2nãobnão}{\ displaystyle \ {ca ^ {n} b ^ {n} \} \ xícara \ {da ^ {2n} b ^ {n} \}}{bnãononãovs}∪{bnãono2nãod}{\ displaystyle \ {b ^ {n} a ^ {n} c \} \ xícara \ {b ^ {n} a ^ {2n} d \}}

Linguagens inequívocas

Uma linguagem algébrica é inequívoca ou inequívoca se houver uma gramática inequívoca que a gera. A linguagem que não é inequívoca é inerentemente ambígua .

Toda linguagem determinística é inequívoca, mas as linguagens não ambíguas são fechadas por espelho, portanto, a inclusão é estrita. Existem linguagens algébricas inerentemente ambíguas, como a linguagem . Isso é provado com a ajuda do lema de Ogden . {nonãobnãovsm∣não,m≥0}∪{nonãobmvsm∣não,m≥0}{\ displaystyle \ {a ^ {n} b ^ {n} c ^ {m} \ mid n, m \ geq 0 \} \ cup \ {a ^ {n} b ^ {m} c ^ {m} \ mid n, m \ geq 0 \}}

Teoremas de representação

Três teoremas fornecem uma maneira geral de representar linguagens algébricas.

Teorema de Chomsky-Schützenberger

O teorema afirma que as linguagens de Dyck são linguagens algébricas "típicas".

Chomsky - Teorema de Schützenberger  -  Uma linguagem sobre um alfabeto é algébrica se e somente se houver uma linguagem Dyck , uma linguagem racional e um morfismo alfabético (ou seja, tal que a imagem de uma letra seja uma letra ou a palavra vazia), como eu{\ displaystyle L}NO{\ displaystyle A} D{\ displaystyle D} K{\ displaystyle K}φ{\ displaystyle \ varphi}

eu=φ(D∩K){\ displaystyle L = \ varphi (D \ cap K)}.

Teorema de Shamir

Teorema de Shamir  -  Uma linguagem sobre um alfabeto é algébrica se e somente se existe um alfabeto , uma carta e um morfismo de no conjunto de peças de tal forma que eu{\ displaystyle L}NO{\ displaystyle A}B{\ displaystyle B}b∈B{\ displaystyle b \ in B}Φ{\ displaystyle \ Phi}NO∗{\ displaystyle A ^ {*}}(B∪B¯)∗{\ displaystyle (B \ cup {\ bar {B}}) ^ {*}}

eu={você∈NO∗∣bΦ(você)∩DB∗≠∅}{\ displaystyle L = \ {u \ in A ^ {*} \ mid b \ Phi (u) \ cap D_ {B} ^ {*} \ neq \ emptyset \}}.

Aqui, está uma cópia desconexa de , e é a linguagem de Dyck emB¯{\ displaystyle {\ bar {B}}}B{\ displaystyle B}DB∗{\ displaystyle D_ {B} ^ {*}}B∪B¯{\ displaystyle B \ cup {\ bar {B}}}

O teorema da linguagem mais difícil, de Greibach

A " linguagem mais difícil " foi definida por Sheila Greibach em 1973. É uma linguagem em que o teste de adesão é o mais difícil, no sentido de que qualquer algoritmo de teste de adesão se traduz em um teste de adesão para qualquer outra linguagem algébrica.

Dada uma linguagem sobre um alfabeto , a versão não determinística de e a linguagem denotada definida como segue. Acrescentamos às três novas letras . Neste novo alfabeto, consideramos a linguagem . Qualquer palavra de admite uma fatoração eu{\ displaystyle L}NO{\ displaystyle A}eu{\ displaystyle L}NÃO(eu){\ displaystyle N (L)}NO{\ displaystyle A}[,],+{\ displaystyle [,], {+}}K=([(NO∗+)∗NO∗])∗{\ displaystyle K = ([(A ^ {*} {+}) ^ {*} A ^ {*}]) ^ {*}}h{\ displaystyle h}K{\ displaystyle K}

h=[h1][h2]⋯[hnão]{\ displaystyle h = [h_ {1}] [h_ {2}] \ cdots [h_ {n}]}

e cada palavra é escrita na forma heu{\ displaystyle h_ {i}}

heu=heu,1+heu,2+⋯+heu,keu{\ displaystyle h_ {i} = h_ {i, 1} {+} h_ {i, 2} {+} \ cdots {+} h_ {i, k_ {i}}}

onde as palavras estão no alfabeto . A escolha de uma palavra heu,j{\ displaystyle h_ {i, j}}NO{\ displaystyle A}h{\ displaystyle h}

h1,j1h2,j2⋯hnão,jnão{\ displaystyle h_ {1, j_ {1}} h_ {2, j_ {2}} \ cdots h_ {n, j_ {n}}}

obtido escolhendo um fator em cada um . Observe o conjunto de opções em . A versão não determinística de é definida por heu,jeu{\ displaystyle h_ {i, j_ {i}}}[heu]{\ displaystyle [h_ {i}]}χ(h){\ displaystyle \ chi (h)}h{\ displaystyle h}eu{\ displaystyle L}

NÃO(eu)={h∣χ(h)∩eu≠∅}{\ displaystyle N (L) = \ {h \ mid \ chi (h) \ cap L \ neq \ emptyset \}}

A linguagem mais difícil é por definição a linguagem que é a versão não determinística da linguagem de Dyck em dois pares de parênteses. H{\ displaystyle H}D2∗{\ displaystyle D_ {2} ^ {*}}

Teorema da linguagem mais difícil (Greibach)  -  Uma linguagem sobre um alfabeto é algébrica se e somente se houver um morfismo tal que temos eu{\ displaystyle L}NO{\ displaystyle A}φ{\ displaystyle \ varphi}

$eu=φ-1(H){\ displaystyle \ $ L = \ varphi ^ {- 1} (H)},

onde está o idioma mais difícil e é uma letra que não está em . H{\ displaystyle H}${\ displaystyle \ $}NO{\ displaystyle A}

A terminologia vem do fato de que o teste de pertencimento de uma palavra à é reduzido ao teste de pertencimento da palavra à linguagem . Assim, qualquer algoritmo de teste de pertinência fornece um algoritmo de teste de pertinência geral, para linguagens algébricas, da mesma complexidade. Extensões do teorema para gramáticas mais gerais foram propostas por Alexander Okhotin. x{\ displaystyle x}eu{\ displaystyle L}φ($x){\ displaystyle \ varphi (\ $ x)}H{\ displaystyle H}H{\ displaystyle H}

Linguagem algébrica e teoria da complexidade

Qualquer linguagem algébrica é decidida por um algoritmo determinístico no espaço O (log 2 n ) e em tempo superpolinomial. Em outras palavras, a classe de linguagens algébricas está incluída no DSPACE (log 2 n ). Qualquer linguagem Dyck é decidida por um algoritmo determinístico no espaço O (log n ). Da mesma forma para idiomas entre parênteses. Qualquer linguagem algébrica determinística não racional precisa de pelo menos log n células de memória para ser decidida.

Qualquer linguagem algébrica é decidida por um algoritmo determinístico no espaço O (log 2 n ) e em tempo polinomial. Assim, qualquer linguagem algébrica está na classe SC .

Bibliografia

Pela natureza fundamental desta noção, muitos trabalhos teóricos sobre computador contêm pelo menos uma seção sobre linguagens algébricas. Vários livros também foram traduzidos para o francês.

Livros em francês

• Alfred Aho , Monica Lam, Ravi Sethi e Jeffrey Ullman ( trad.  Do inglês), Compilers: Principles, Techniques and Tools: With more than 200 years , Paris, Pearson ,2007, 2 nd  ed. , 928  p. ( ISBN  978-2-7440-7037-2 e 2744070378 )
• Pierre Wolper , Introdução à calculabilidade: cursos e exercícios corrigidos , Paris, Dunod ,2006, 3 e  ed. , 224  p. ( ISBN  2-10-049981-5 ).
• Jean-Michel Autebert, línguas algébricas , Masson,1987, 278  p. ( ISBN  978-2-225-81087-9 )
• Olivier Carton , linguagens formais, computabilidade e complexidade ,2008[ detalhe da edição ] ( leia online )
• Jean-Michel Autebert, Jean Berstel e Luc Boasson, “Linguagens livres de contexto e autômatos pushdown” , em G. Rozenberg, A. Salomaa (editores), Handbook of Formal Languages , vol.  1: palavra, idioma, gramática , Springer Verlag,1997( ISBN  978-3540604204 ) , p.  111-174

Livro em alemão

• (de) Katrin Erk e Lutz Priese, Theoretische Informatik: eine umfassende Einführung , Berlin, Springer,2008, 485  p. ( ISBN  978-3-540-76319-2 , OCLC  244015158 ).

Livros em ingles

• (pt) Seymour Ginsburg , The Mathematical Theory of Context Free Languages , McGraw-Hill,1966, ix + 232  p. - O primeiro livro sobre linguagens algébricas.
• (pt) Alfred V. Aho e Jeffrey D. Ullman , A teoria da análise, tradução e compilação , vol.  1: Parsing , Englewood Cliffs, NJ, Prentice-Hall,1972, xii + 543  pág. ( ISBN  0-13-914556-7 )
• (pt) Alfred V. Aho e Jeffrey D. Ullman, A teoria da análise, tradução e compilação , vol.  2: Compilação , Englewood Cliffs, NJ, Prentice-Hall,1973, xii + 460  pág. ( ISBN  0-13-914564-8 )
• (pt) Michael A. Harrison , Introdução à Teoria da Linguagem Formal , Leitura, Mass., Addison-Wesley ,1978, 594  p. ( ISBN  0-201-02955-3 , OCLC  266962302 ).
• (pt) John E. Hopcroft , Rajeev Motwani e Jeffrey D. Ullman, Introdução à Teoria dos Autômatos, Linguagens e Computação , Addison Wesley,2001, 2 nd  ed. , 521  p. ( ISBN  978-0-201-44124-6 e 0201441241 ).
• (pt) Peter Linz, Uma Introdução às Linguagens Formais e Autômatos , Jones & Bartlett Learning,2001, 410  p. ( ISBN  978-0-7637-1422-2 e 0763714224 , leia online ).

Aulas

• Anca Muscholl, “  Linguagem livre de contexto  ” [PDF]
• Jean-François Perrot, "  grammars" Context-Free "and the Chomsky hierarchy  "
• Jean Privat, "  Gramáticas não contextuais  " [PDF] ,15 de março de 2012
• Jacques Désarménien, “  Gramáticas não contextuais  ” [PDF]

Notas

1. Traduções aceitas no Termium Plus , banco de dados lingüísticos e terminológicos do Governo do Canadá .
2. Hopcroft, Motwani e Ullman 2001 , Capítulo 7, p.  285 .
3. Hopcroft, Motwani e Ullman 2001 , Capítulo 7, p.  296 .
4. Hopcroft, Motwani e Ullman 2001 , Capítulo 7, p.  302 .
5. Wolper 2006 , Seção 4.4.4, p.  97
6. Autebert, Berstel, Boasson (1997)
7. Alexander Okhotin , “  Hardest languages ​​for conjuntive and Boolean grammars,  ” Information and Computation , vol.  266,2019, p.  1-18 ( ISSN  0890-5401 , DOI  10.1016 / j.ic.2018.11.001 ).
8. PM Lewis , RE Stearns e J. Hartmanis , "  Limites de memória para o reconhecimento de linguagens livres de contexto e sensíveis ao contexto  ", 6º Simpósio Anual sobre Teoria de Circuito de Comutação e Design Lógico (SWCT 1965) ,Outubro de 1965, p.  191-202 ( DOI  10.1109 / FOCS.1965.14 , ler online , acessado em 17 de outubro de 2017 ).
9. RW Ritchie e FN Springsteel , “  Language Recognition by selection automata,  ” Information and Control , vol.  20, n o  4,1 ° de maio de 1972, p.  313–330 ( DOI  10.1016 / S0019-9958 (72) 90205-7 , ler online , acessado em 17 de outubro de 2017 ).
10. Nancy Lynch , "  Log Space Recognition and Translation of Parenthesis Languages  ", J. ACM , vol.  24, n o  4,Outubro de 1977, p.  583-590 ( ISSN  0004-5411 , DOI  10.1145 / 322033.322037 , ler online , acessado em 17 de outubro de 2017 ).
11. Alt, Helmut , Mehlhorn, Kurt , Michaelson, S. e Milner, R. , "Lower Bounds for the Space Complexity of Context-Free Recognition" , no Terceiro Colóquio Internacional sobre Autômatos, Línguas e Programação ,1976( leia online ).
12. Stephen A. Cook , "  Deterministic CFL's Are Accepted Simulttically in Polynomial Time and Log Squared Space  ", Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing , ACM, sTOC '79,1979, p.  338-345 ( DOI  10.1145 / 800135.804426 , ler online , acessado em 17 de outubro de 2017 ).

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">