| dbpedia-owl:abstract
|
- Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA kann ein um einen konstanten Faktor größeres Band simulieren, indem das Bandalphabet -Tupel des Eingabealphabetes enthält. Entsprechend wäre auch eine Definition denkbar, bei der gleich ein um einen konstanten Faktor größeres Band vorgesehen wird. Das heißt, es gibt eine konstante Zahl, so dass die Turingmaschine höchstens die ersten Felder des Bandes benutzt, wobei die Länge des Eingabewortes ist. Die nutzbare Bandlänge ist dann also linear in der Länge der Eingabe. Dies erklärt das "Linear" im Namen der LBA. Die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen. Es ist ein offenes Problem, ob deterministische LBAs die gleiche Sprachklasse akzeptieren wie die nichtdeterministischen.
- In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of nondeterministic Turing machine.
- 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.
- 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.
- 線形拘束オートマトン（せんけいこうそく-、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存言語によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。
- Automat liniowo ograniczony (ang. linear bounded automaton) to 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.
- 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. 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 1][2 2] e [3 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 ∪ {<, >}) → 2 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 <e >, 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). Não se sabe se a versão não determinística desta máquina aumenta ou não o poder computacional das Máquinas de Turing com Memória Limitada. Predefinição:Carece de fontes
- 线性有界自动机(简写 LBA)是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它不同于图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。 线性有界自动机是上下文有关语言的接受器。对这种语言在文法上的唯一限制是没有把字符串映射成更短字符串的产生式。所以在上下文有关语言中没有字符串的推导可以包含比字符串自身更长的句子形式。因为在线性有界自动机和这种文法之间的一一对应，对于要被自动机识别的字符串不需要比原始字符串所占用的更多的磁带。
- 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 assujettie à des restrictions dans son mode opératoire.
|
| rdfs:comment
|
- In computer science, a linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of nondeterministic Turing machine.
- 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.
- 線形拘束オートマトン（せんけいこうそく-、Linear Bounded Automaton）は、制限されたチューリングマシンである。LBA と略記される。有限種類の文字を保持できるテープとそのテープの読み書きができるヘッドを持ち、有限数の状態を持つ。チューリングマシンと異なるのは LBA のテープ長が有限であることで、その長さはテープ上の初期入力文字列の長さに比例する（つまり一次関数である）。この制限により LBA はある意味ではチューリングマシンよりも実在のコンピュータの正確なモデルと言える。 線形拘束オートマトンは文脈依存言語を受容する。そのクラスの言語の文法で制限されていることは、ある文字列から短い別の文字列へのマッピングを持たないことである。したがって、文脈依存言語によって生成される文字列は、それ自身より長い文型を内包することができない。線形拘束オートマトンと文脈依存言語は一対一の対応関係にあるので、本来の文字列が書かれたテープの長さがあれば、そのオートマトンに理解できる文字列には必要十分である。
- Automat liniowo ograniczony (ang. linear bounded automaton) to 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.
- 线性有界自动机(简写 LBA)是受限形式的非确定图灵机。它拥有由包含来自有限字母表的符号的单元构成的磁带，可以一次读取和写入磁带上一个单元的并可以移动的磁头，和有限数目个状态。它不同于图灵机在于尽管磁带最初被认为是无限的，只有其长度是初始输入的线性函数的有限临近部分可以被读写磁头访问。这个限制使 LBA 成为在某些方面比图灵机更接近实际存在的计算机的精确模型。 线性有界自动机是上下文有关语言的接受器。对这种语言在文法上的唯一限制是没有把字符串映射成更短字符串的产生式。所以在上下文有关语言中没有字符串的推导可以包含比字符串自身更长的句子形式。因为在线性有界自动机和这种文法之间的一一对应，对于要被自动机识别的字符串不需要比原始字符串所占用的更多的磁带。
- Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA kann ein um einen konstanten Faktor größeres Band simulieren, indem das Bandalphabet -Tupel des Eingabealphabetes enthält. Entsprechend wäre auch eine Definition denkbar, bei der gleich ein um einen konstanten Faktor größeres Band vorgesehen wird.
- 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).
- 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.
- 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 assujettie à des restrictions dans son mode opératoire.
|
