Формальные грамматики и языки - Гладкий А.В.
Скачать (прямая ссылка):
Lesniewski S. Grundziige eines neuen Systems der Grund-lagen der Mathematik. — Fundam. Math., 1929, 14, 1—81.
Marcus S. Algebraic linguistics; analytical models. — N. Y. — L., 1967. (Русский перевод: Маркус С., Теоретико-множественные модели языков, «Наука», 1970.)
М у h i 11 J. Finite automata and the representation of events. — WADC Technical Report 57—624, 1957, 112—137.
N e г о d e A. Linear automaton transformations. — Proc. Amer. Math. Soc., 1958, 9, № 4, 541—544.
Novotny M. Ober endlich characterisierbare Sprachen. — Spi-sy pripodoved. fak. univ. v Brne, 1965 (a), № 10, 495—502.
Novotny M. Bemerkung fiber ableitbare Sprachen. — Spisy pfirodoved. fak. univ. v Brne, 1965 (6), Ns 10, 503—507.
Novotny M. Bemerkungen iiber Homorphismen von Spra^ chen. — Spisy pfirodoved. fak. univ. v Вгпё, 1965 (в), № 10, 509— 518.
P a r i k h R. J. Language generating devices. — М. I. T. Res. Lab. Electron. Quart. Prog. Rept, 1961, № 60, 199—212.
Parikh R. J. On context-free languages.—J. Assoc. Computing Machinery, 1966, 13, № 4, 570—580.
Post E. L. A variant of a recursively unsolvable problem. — Bull. Amer. Math. Soc., 1946, 52, № 4, 264—268.
Rabin M. O. Speed of computation of function and classifica' tion of recursive sets. — Bull. Res. Council Israel, 1959, 8F, 69—70.
Rabin M. O. Real-time computation. —"Israel Journal Math-1963, 1, № 4, 203—211.
356
ЛИТЕРАТУРА
Rabin М. О., S с о 11 D. Finite automata and their decision problems.— IBM Journal Res. and Devel., 1959, 3, № 2, 114—125. (Русский перевод: Рабин М., Скотт Д., Конечные автоматы и проблемы их разрешения, Кибернетический сборник, вып. 4, ИЛ, 1962, 56—91.)
Rice Н. G. Classes of recursive enumerable sets and their decision problems. — Trans. Amer. Math. Soc., 1953, 74, № 2, 358—366.
Ritchie R. W. Classes of predictible computable functions. — Trans. Amer. Math. Soc., 1963, 106, № 1, 139—173. (Русский перевод: Ричи P. В., Классы предсказуемо вычислимых функций, сб. «Проблемы математической логики», «Мир», 1970, 50—93.)
Rosenberg A. L. A machine realisation of the linear context-free languages. — Information and Control, 1967, 10, № 2, 175—188.
Samel son K-, Bauer F. L., Sequential formula translation. — Commun. Assoc. Computing Machinery, 1960, 3, № 2, 76—83.
Scheinberg S. Note on the Boolean properties of context-free languages. — Information and Control, 1960, 3, № 4, 372—375.
Schiitzenberger M. P. On context-free languages and pushdown automata. — Information and Control, 1963, 6, № 3, 246— 264.
Schiitzenberger M. P. Une probleme de la theorie des automates.— Seminaire Dubreil—Pisot, Paris, 1959.
Schiitzenberger M. P. Some remarks on Chomsky’s context-free languages. — М. I. T. Res. Lab. Electron. Quart. Prog. Rept., 1961, № 63, 155—170.
Shamir E. A remark of discovery algorithms for grammars. — Information and Control. 1962, 5, № 3, 246—251.
Shannon К- E. A mathematical theory of communication. — Bell System Techn. Journal, 1948, 27, № 3, 379—423; № 4, 623—656. (Русский перевод: Шеннон К., Математическая теория связи, сб. «Работы по теории информации и кибернетике», ИЛ, 1963, 249—332.)
Tesniere L. Elements de syntaxe structurale. Paris, 1959.
Turing A. M. On computable numbers, with an application to the Entscheidungsproblem. — Proc. London Math. Soc., ser. 2, 1936— 1937, 42, 230—265. A correction, ibid., 1937, 43, 544—546.
U11 i a n J. S. Failure of a conjecture about context-free languages.— Information and Control, 1966, 9, № 1, 61—65.
Wells R. S. Immediate constituents. — Language, 1947, 23, № 2, 81—117.
Yngve V. H. A model and a hypothesis for language structure. Proc. Amer. Phil. Soc., 1960, 104, № 5, 444—466.
Yntema М. K. Inclusion relations among families of context-free languages. — Information and Control, 1967, 10, № 6, 572—597.
ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ
Автомат древообходящий
( = Д-автомат) 140
— конечный 159
---двуленточный (=ДК-авто-
мат) 182
---с выходом 180
А-грамматика, см. Грамматика автоматная 29 Алгоритм 252
— для распознавания конечности Б-языка 124
— — •— пустоты Б-языка 122 Алфавит, см. Словарь 19, 27 Анализатор предсказуемостный
141
A-язык, см. Язык автоматный 30
База линейного множества векторов 129
— полулинейного множества векторов 130
Б-грамматика, см. Грамматика бесконтекстная 29
Биграф 19
— нагруженный 19
Б-ОАЕ-грамматика, см. Грамматика бесконтекстная ограниченной активной емкости 234
Б-правило, см. Правило бесконтекстное 29
Буква, см. Символ элементарный 19
Б-язык, см. Язык бесконтекстный
30
Вектор 129
Вершина (графа), см. Узел графа 18
Взаимозамещаемость 318
Вкладываться (Ъ-грамматика вкладывается в JX-граммати-ку) 201
Вложена непосредственно (составляющая В непосредственно вложена в составляющую А) 286 Время работы (Э-машины) 63 Вхождение отмеченное 200
— символа 21
— цепочки 21 Вывод 28
— бесповторный 31
— полный 28
—, приведенный налево 51
— размеченный 28 упорядоченный 31
— упорядочиваемый 31 Выводимость (цепочка г| выводима из ш) 28
— непосредственная 28 Выводы равносильные, см. Равносильность выводов 31
