| dbo:abstract
|
- Un autòmat linealment acotat , abreujadament LBA (de l'anglès, Linear bounded automaton ), o ALA és un autòmat similar a una màquina de Turing determinista. (ca)
- Pojem lineárně ohraničený Turingův stroj označuje v informatice Turingův stroj, který má omezení při zápisu na pásku. Na rozdíl od běžného Turingova stroje totiž nesmí zapisovat na neomezeně mnoho buněk pásky, ale pouze na prvních n buněk, kde n je omezeno lineární funkcí vzhledem k délce vstupního slova. V určitém smyslu je tak tento stroj bližší běžným počítačům. Lineárně ohraničené Turingovy stroje umí akceptovat jazyky ze třídy kontextových jazyků. Lze dokázat, že pro každý lineárně ohraničený Turingův stroj lze sestrojit Turingův stroj, který nepotřebuje pásku delší než je délka vstupního slova. (cs)
- Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des Bandes, auf dem die Eingabe steht, während der gesamten Berechnung nicht verlässt. (de)
- In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. (en)
- En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée. (fr)
- Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton),o ALA es un autómata similar a una máquina de Turing determinista. (es)
- Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky). Come una macchina di Turing, il nastro di un LBA è composto da celle che possono contenere simboli appartenenti ad un alfabeto finito. L'automa possiede un numero finito di stati e la sua testina può leggere e scrivere una sola cella per volta. (it)
- 컴퓨터 과학에서 선형유한 자동 기계(linear bounded automaton, LBA)는 계산 능력을 제한한 튜링 기계의 일종이다. (ko)
- 線形拘束オートマトン（せんけいこうそくオートマトン、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存文法によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。 (ja)
- Automat liniowo ograniczony (ang. linear bounded automaton) – ograniczona wersja maszyny Turinga, która podczas obliczenia na słowie wejściowym długości n może wykorzystać jedynie O(n) komórek taśmy. Innymi słowy, dostępna pamięć jest funkcją liniową od długości wejścia. Można także powiedzieć, że może ona w trakcie działania wykorzystywać tylko te komórki na taśmie, w których zapisane jest słowo wejściowe. (pl)
- Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto. Sua fita é limitada e portanto finita. Ele só consegue resolver problemas que usem uma quantidade de memória que possa caber dentro da fita usada para entrada. Se por acaso utilizarmos um alfabeto de fita maior que o alfabeto de entrada então teremos um incremento da memória disponível por até um fator constante, por isso se tivermos uma entrada de tamanho n a quantidade de memória disponível será linear em relação a n. Apesar de suas restrições os ALLs são bastantes potentes, podemos citar que os decisores para o problema da aceitação de um AFD para uma dada entrada, para o problema da vacuidade de um dado AFD, para o problema da aceitação de uma gramática livre de contexto e para a vacuidade de uma dada gramática livre de contexto são todos ALLs. O Autômato Linearmente Limitado é um formalismo reconhecedor não determinístico, o qual pode ser definido por uma óctupla (Σ, S, δ, S0, F, V, <, >), [1][2] e [3] onde:
* Σ é o alfabeto de símbolos de entrada;
* S é o conjunto de estados possíveis, o qual é finito;
* δ é o programa ou função de transição
* δ: S × (Σ ∪ V ∪ {<, >}) → 2S × (Σ ∪ V ∪ {<, >}) × {E, D} a qual é uma função parcial;
* S0 é o estado inicial da máquina, S0 ∈ S;
* F é o conjunto de estados finais, F ⊂ S;
* V é o alfabeto auxiliar (pode ser vazio);
* < é o símbolo especial marcador de início da fita;
* > é o símbolo especial marcador de fim da fita. O ALL possui uma fita de entrada a qual tem tamanho finito e é delimitada pelos símbolos , possui também um cabeçote de Leitura/Escrita, o qual tem a posição inicial sempre na primeira célula a direita do símbolo á, sempre que o cabeçote lê um símbolo ele deve escrever outro na mesma célula e mover-se para esquerda ou para direita. Como tem caráter não determinístico os estados podem ter mais de uma saída com o mesmo símbolo, quando isso ocorre uma ‘cópia’ do ALL é criada e executada simultaneamente, a primeira ‘cópia’ que parar em um estado final é aceita, e as outras são excluídas. A transição é representada por (símbolo lido, símbolo a ser escrito, direção para qual o cabeçote de leitura/escrita deve ir). Uma característica importante dos ALLs é que um ALL pode ter somente um número limitado de configurações dado que a entrada tem tamanho n. Dado que a entrada tem tamanho n, seja M um ALL com "q" estados e "s" símbolos no alfabeto da fita então podemos dizer que existem exatamente "q*n*s^n" configurações distintas de M. (pt)
- 线性有界自动机（英文：Linear bounded automaton，简写： LBA）是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。 (zh)
|
| rdfs:comment
|
- Un autòmat linealment acotat , abreujadament LBA (de l'anglès, Linear bounded automaton ), o ALA és un autòmat similar a una màquina de Turing determinista. (ca)
- Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des Bandes, auf dem die Eingabe steht, während der gesamten Berechnung nicht verlässt. (de)
- In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of Turing machine. (en)
- En informatique théorique, et en particulier en théorie des automates, un automate linéairement borné (en anglais linear bounded automaton, abrégé en LBA) est une machine de Turing non déterministe qui n'utilise qu'une portion contiguë du ruban de taille linéaire en la taille de l'entrée. (fr)
- Un autómata linealmente acotado, abreviadamente LBA (del inglés, Linear Bounded Automaton),o ALA es un autómata similar a una máquina de Turing determinista. (es)
- 컴퓨터 과학에서 선형유한 자동 기계(linear bounded automaton, LBA)는 계산 능력을 제한한 튜링 기계의 일종이다. (ko)
- 線形拘束オートマトン（せんけいこうそくオートマトン、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存文法によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。 (ja)
- Automat liniowo ograniczony (ang. linear bounded automaton) – ograniczona wersja maszyny Turinga, która podczas obliczenia na słowie wejściowym długości n może wykorzystać jedynie O(n) komórek taśmy. Innymi słowy, dostępna pamięć jest funkcją liniową od długości wejścia. Można także powiedzieć, że może ona w trakcie działania wykorzystywać tylko te komórki na taśmie, w których zapisane jest słowo wejściowe. (pl)
- 线性有界自动机（英文：Linear bounded automaton，简写： LBA）是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它区别于更为普遍的图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。 (zh)
- Pojem lineárně ohraničený Turingův stroj označuje v informatice Turingův stroj, který má omezení při zápisu na pásku. Na rozdíl od běžného Turingova stroje totiž nesmí zapisovat na neomezeně mnoho buněk pásky, ale pouze na prvních n buněk, kde n je omezeno lineární funkcí vzhledem k délce vstupního slova. V určitém smyslu je tak tento stroj bližší běžným počítačům. (cs)
- Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica in cui la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare i linguaggi dipendenti dal contesto generati da grammatiche sensibili al contesto (o di Tipo-1 secondo la gerarchia di Chomsky). (it)
- Um Autômato linearmente limitado é uma Máquina de Turing com memória limitada e é o mecanismo reconhecedor de Linguagens sensíveis ao contexto. Sua fita é limitada e portanto finita. Ele só consegue resolver problemas que usem uma quantidade de memória que possa caber dentro da fita usada para entrada. Se por acaso utilizarmos um alfabeto de fita maior que o alfabeto de entrada então teremos um incremento da memória disponível por até um fator constante, por isso se tivermos uma entrada de tamanho n a quantidade de memória disponível será linear em relação a n. Apesar de suas restrições os ALLs são bastantes potentes, podemos citar que os decisores para o problema da aceitação de um AFD para uma dada entrada, para o problema da vacuidade de um dado AFD, para o problema da aceitação de uma (pt)
|
