Какой язык называется распознаваемым: Распознаваемый язык — это… Что такое Распознаваемый язык?

Содержание

Распознаваемый язык - это... Что такое Распознаваемый язык?

  • Рекурсивно перечислимый язык — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источни …   Википедия

  • ФОРМАЛЬНЫЙ ЯЗЫК, ПРЕДСТАВИМЫЙ МАШИНОЙ — формальный язык, распознаваемый машиной, множество всех тех слов, при работе над к рыми машина попадает в одно из выделенных состояний. Всякое рекурсивно перечислимое множество слов есть формальный язык (ф. я.), представимый нек рой Тьюринга… …   Математическая энциклопедия

  • Видеонаблюдение — Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Викифицировать статью …   Википедия

  • Портрет — Питер Пауль Рубенс. «Портрет камеристки инфанты Изабеллы» …   Википедия

  • Класс PH — В теории алгоритмов классом сложности PH (от англ. polynomial hierarchy) называется объединение всех классов сложности из полиномиальной иерархии: Таким образом, предикат принадлежит классу PH, если существует такое k, что предикат принадлежит… …   Википедия

  • Класс ZPP — В теории вычислительной сложности, ZPP (zero error probabilistic polynomial time  безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам:… …   Википедия

  • ZPP — В теории вычислительной сложности, ZPP (zero error probabilistic polynomial time безошибочный вероятностный полиномиальный) это такой класс задач, для которых существует вероятностная машина Тьюринга, удовлетворяющая нескольким свойствам: Она… …   Википедия

  • АДИАГНОСТИЧЕСКИЙ — (от греч. a отриц. част., и diagnosis различение). В медицине: не распознаваемый или трудно различаемый недуг. Словарь иностранных слов, вошедших в состав русского языка. Чудинов А.Н., 1910. АДИАГНОСТИЧЕСКИЙ от греч. а, отриц. част., и diagnosis …   Словарь иностранных слов русского языка

  • НОУ ИНТУИТ | Лекция | Конечные автоматы

    Аннотация: В данной лекции рассматриваются два наиболее распространенных способа конечного задания формального языка: грамматики и автоматы. Рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам, определяются понятия конечного автомата, недетерминированного конечного автомата и распознаваемого конечным автоматом языка. Приведены практические примеры и упражнения для закрепления материала

    Два наиболее распространенных способа конечного задания формального языка - это грамматики и автоматы. Автоматами в данном контексте называют математические модели некоторых вычислительных устройств. В этой лекции рассматриваются конечные автоматы, соответствующие в иерархии Хомского праволинейным грамматикам. Более сильные вычислительные модели будут определены позже, в лекциях "10" , "14" и "15" . Термин "автоматный язык" закреплен за языками, распознаваемыми именно конечными автоматами, а не какими-либо более широкими семействами автоматов (например, автоматами с магазинной памятью или линейно ограниченными автоматами).

    В разделе 2.1 определяются понятия конечного автомата (для ясности такой автомат можно называть недетерминированным конечным автоматом) и распознаваемого конечным автоматом языка. В следующем разделе дается другое, но эквивалентное первому определение языка, распознаваемого конечным автоматом. Оно не является необходимым для дальнейшего изложения, но именно это определение поддается обобщению на случаи автоматов других типов.

    В разделе 2.3 доказывается, что тот же класс автоматных языков можно получить, используя лишь конечные автоматы специального вида (они читают на каждом такте ровно один символ и имеют ровно одно начальное состояние). Во многих учебниках конечными автоматами называют именно такие автоматы.

    Целую серию классических результатов теории формальных языков составляют теоремы о точном соответствии некоторых классов грамматик некоторым классам автоматов. Первая теорема из этой серии, утверждающая, что праволинейные грамматики порождают в точности автоматные языки, доказывается в разделе 2.4.

    Другая серия результатов связана с возможностью сузить некоторый класс грамматик, не изменив при этом класс порождаемых ими языков. Обычно в таком случае грамматики из меньшего класса называются грамматиками в нормальной форме. В разделе 2.5

    * формулируется результат такого типа для праволинейных грамматик. Сама эта теорема не представляет большого интереса, но аналогичные результаты, доказываемые позже для контекстно-свободных грамматик, используются во многих доказательствах и алгоритмах.

    Не все конечные автоматы подходят для конструирования распознающих устройств, пригодных для практических приложений, так как в общем случае конечный автомат не дает точного указания, как поступать на очередном шаге, а разрешает продолжать вычислительный процесс несколькими способами. Этого недостатка нет у детерминированных конечных автоматов (частного случая недетерминированных конечных автоматов), определенных в разделе 2.6. В разделе 2.7 доказывается, что каждый автоматный язык задается некоторым детерминированным конечным автоматом.

    2.1. Недетерминированные конечные автоматы

    Определение 2.1.1. Конечный автомат (finite automaton, finite-state machine) - это пятерка , где - конечный

    входной алфавит (или просто алфавит ) данного конечного автомата, и - конечные множества,

    , . Элементы Q называются состояниями (state), элементы I - начальными (initial) состояниями, элементы F - заключительными или допускающими (final, accepting) состояниями. Если , то называется переходом (transition) из p в q, а слово x - меткой (label) этого перехода.

    Пример 2.1.2. Пусть Q = {1,2}, , I = {1}, F = {2},

    Тогда - конечный автомат.

    Замечание 2.1.3. Конечные автоматы можно изображать в виде диаграмм состояний (state diagram) (иногда их называют диаграммами переходов (transition diagram)). На диаграмме каждое состояние обозначается кружком, а переход - стрелкой. Стрелка из p в q, помеченная словом x, показывает, что является переходом данного конечного автомата. Каждое начальное состояние распознается по ведущей в него короткой стрелке. Каждое допускающее состояние отмечается на диаграмме двойным кружком.

    Пример 2.1.4. На диаграмме изображен конечный автомат из примера 2.1.2.

    Замечание 2.1.5. Если в конечном автомате имеются несколько переходов с общим началом и общим концом, то такие переходы называются параллельными. Иногда на диаграмме состояний конечного автомата параллельные переходы изображают одной стрелкой. При этом метки переходов перечисляют через запятую.

    Пример 2.1.6. На диаграмме снова изображен конечный автомат из примера 2.1.2.

    Определение 2.1.7. Путь (path) конечного автомата - это кортеж , где и для каждого i. При этом q0 - начало пути qn - конец пути n - длина пути w1...wn - метка пути.

    Замечание 2.1.8. Для любого состояния существует путь . Его метка - , начало и конец совпадают.

    Определение 2.1.9. Путь называется успешным если его начало принадлежит I, а конец принадлежит F.

    Пример 2.1.10. Рассмотрим конечный автомат из примера 2.1.2. Путь является успешным. Его метка - baaab. Длина этого пути - 4.

    Определение 2.1.11. Слово w допускается (is accepted, is recognized) конечным автоматом M, если оно является меткой некоторого успешного пути.

    Определение 2.1.12. Язык, распознаваемый конечным автоматом M, - это язык L(M), состоящий из меток всех успешных путей (то есть из всех допускаемых данным автоматом слов). Будем также говорить, что автомат M распознает (recognizes, accepts) язык L(M).

    Замечание 2.1.13. Если , то язык, распознаваемый конечным автоматом , содержит .

    Пример 2.1.14. Пусть , где Q = {1,2}, , I = {1}, F = {1,2},

    Тогда

    Определение 2.1.15. Два конечных автомата эквивалентны, если они распознают один и тот же язык.

    Определение 2.1.16. Язык L называется автоматным (finite-state language), если существует конечный автомат, распознающий этот язык.

    Замечание 2.1.17. Обычно в учебниках используется более узкое определение недетерминированного конечного автомата, но это не меняет класса автоматных языков (см. лемму 2.3.3.).

    Пример 2.1.18. Рассмотрим однобуквенный алфавит . При любых фиксированных и язык является автоматным.

    Замечание 2.1.19. Каждый конечный язык является автоматным.

    Определение 2.1.20. Состояние q достижимо (reachable) из состояния p, если существует путь, началом которого является p, а концом - q.

    Лемма 2.1.21. Каждый автоматный язык распознается некоторым конечным автоматом, в котором каждое состояние достижимо из некоторого начального состояния и из каждого состояния достижимо хотя бы одно заключительное состояние.

    Пример 2.1.22. Рассмотрим конечный автомат , где Q = {1,2,3,4}, , I = {1,2,4}, F = {1,3,4},

    Удалим те состояния (и содержащие их переходы), которые не удовлетворяют требованиям леммы 2.1.21. Получается эквивалентный конечный автомат , где Q' = {1,4}, I' = {1,4}, F' = {1,4},

    Замечание 2.1.23 Естественным обобщением конечного автомата является конечный преобразователь (finite-state transducer), позволяющий на каждом такте отправить несколько символов в дополнительный "выходной" поток. В некоторых книгах конечными автоматами называют именно такие устройства (с выходным потоком).

    В данном пособии конечные преобразователи рассматриваться не будут.

    Упражнение 2.1.24. Найти конечный автомат, распознающий язык

    Упражнение 2.1.25. Найти конечный автомат, распознающий язык

    Упражнение 2.1.26. Найти конечный автомат, распознающий язык

    Упражнение 2.1.27

    . Найти конечный автомат, распознающий язык

    Упражнение 2.1.28. Найти конечный автомат, распознающий язык

    Упражнение 2.1.28. Найти конечный автомат, распознающий язык , где , и для любого

    Конечные автоматы, потоковые алгоритмы и машины Тьюринга

    Часть III. Языки, грамматики, автоматы

    Часть III Языки, грамматики, автоматы 137 Глава 10 Языки и конечные автоматы 10.1 Язык Дика Как мы знаем, правильные скобочные структуры перечисляются числами Каталана. Выпишем все правильные скобочные

    Подробнее

    Занятие 7. Лемма 1. Для любых чисел a, b, q. 1. если a 0 или b 0, то существует d, т. ч. d = (a, b), причем (a, b) > 0;

    Занятие 7 Число d называется наибольшим общим делителем (НОД) чисел a и b, если (1) d a и d b, а также (2) для всех x из x a и x b следует x d. В этом случае пишем d = (a, b). Лемма 1. Для любых чисел

    Подробнее

    2 l 1. 2 l. l+1 n LS(n) 2 n 1.

    Автоматные модели защищенных компьютерных систем А. В. Галатенко В работе рассматривается автоматная система, часть состояний которой объявляется безопасной. Исследуются языки, не выводящие автомат из

    Подробнее

    Вычислимость лекция 10

    Вычислимость лекция 10 Лев Дмитриевич Беклемишев http://lpcs.math.msu.su/vml2009 [email protected] 16.04.2009 Машины Тьюринга Опр. Машина Тьюринга задаётся конечными рабочим алфавитом Σ, содержащим символ

    Подробнее

    Построение ДКА п о регулярному автомату.

    Семинарское занятие по практикуму для 2 курса 290406 План 1 Построение ДКА по регулярному выражению 2 Лемма о разрастании для регулярных множеств 3 Лемма о разрастании для контекстно свободных языков Построение

    Подробнее

    Лекция 16. Универсальная машина Тьюринга

    Лекция 16. Универсальная машина Тьюринга Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Важнейшим свойством вычислимых функций является существование универсальной вычислимой

    Подробнее

    Задание 10. LL-анализ

    Задание 10 LL-анализ Ключевые слова 1 :язык, контекстно-свободный язык, магазинный автомат, грамматика, LL(k)-грамматика, LL(1)-анализатор, функции FIRST, FOLLOW. 1 Нисходящий и восходящий разбор Напомним

    Подробнее

    Вычислимость лекция 11

    Вычислимость лекция 11 Лев Дмитриевич Беклемишев http://lpcs.math.msu.su/vml2010 [email protected] 22.04.2009 Теорема Поста Tеорема. A N разрешимо A и N \ A перечислимы. Доказательство. Пусть определённые

    Подробнее

    E k (n) = E k E k... E

    Решение автоматных уравнений в множестве детерминированных функций И. В. Лялин В данной работе рассматривается задача существования детерминированных функций, являющихся решением заданного автоматного

    Подробнее

    Тема 1-2: Элементы комбинаторики

    Тема 1-2: Элементы комбинаторики А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (1

    Подробнее

    Предположим, алфавит A машины содержит символы B (пробельный), 1, M, I, Q, T, *, S, Y, N и др.

    Проблема останова Формулировка проблемы Может ли быть создана машина H, которая, получая на входной ленте описание некоторой машины D и описание входной ленты машины D, останавливается, и сообщает, остановится

    Подробнее

    Задачи по дискретной математике

    Задачи по дискретной математике Ф.Г. Кораблев 1 Комбинаторика 1.1. Найти число подмножеств X множества {A, B, C, D, E, F, G, H, I, J}, обладающие следующими свойствами: 1. X = 3 2. X = 5, A X 3. X = 6,

    Подробнее

    Формальные грамматики

    Формальные грамматики Основные понятия Алфавит - это конечное множество символов. Цепочка последовательность символов. Терминальная цепочка последовательность терминальных символов. Язык множество терминальных

    Подробнее

    Легко видеть, что D(h) = E(g).

    Занятие 8 Три варианта определения термина «перечислимое множество»: Множество A Σ называется перечислимым, если (Вариант 1) A есть область значений некоторой вычислимой функции. (Вариант 2) A есть область

    Подробнее

    ,

    Занятие 5 Ориентированный граф (или, орграф) G = (V, A) состоит из некоторого непустого множества V вершин и множества A соединяющих эти вершины ориентированных ребер (или, дуг или, стрелок). Мы пишем

    Подробнее

    Диофантовы уравнения 1

    Диофантовы уравнения 1 Теорема (Гаусс. Натуральное число представимо в виде суммы трёх квадратов, если и только если оно не представимо в виде 4 n (8m 1. Вводные задачи Задача 1. Докажите, что уравнения

    Подробнее

    Лекции по теории формальных языков

    Лекции по теории формальных языков Лекция 4. Контекстно-свободные грамматики и языки: определения и примеры. Лемма о накачке Александр Сергеевич Герасимов http://gas-teach.narod.ru Кафедра математических

    Подробнее

    ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК :

    ПРИМЕРЫ ПОСТРОЕНИЯ ГРАММАТИК Порождающие грамматики служат для точного, формального задания языков. На практике часто ставится обратная задача: построить грамматику на основе некоторого числа примеров

    Подробнее

    ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ

    ВВЕДЕНИЕ В ТЕОРИЮ АЛГОРИТМОВ Компьютерная программа делает то, что вы приказали ей сделать, а не то, что вы хотели, чтобы она сделала. Д. Грир Содержание 2 Неформальное определение алгоритма Формальное

    Подробнее

    5. Линейные коды (продолжение)

    17 5. Линейные коды (продолжение) Проверочная матрица кода. Другой способ задания линейного подпространства C F n размерности k состоит в указании n k линейных уравнений, которым удовлетворяют координаты

    Подробнее

    2. Метрические пространства

    2 2. Метрические пространства Одним из часто встречающихся в математике понятий является понятие расстояния. Оно используется в аналитической геометрии при изучении свойств геометрических объектов в евклидовых

    Подробнее

    Дискретная математика 2

    Дискретная математика 2 Сложность по времени (дополнительные темы) Отделение прикладной математики и информатики Высшая школа экономики тделение прикладной математики и информатики Дискретная математика

    Подробнее

    Недетерминированные алгоритмы

    1 Недетерминированные алгоритмы Лекция 1. Определение. Машина Тьюринга - это 1. Конечное множество S (множество состояний). 2. Конечное множество A (алфавит). 3. Конечная таблица (программа) из строк вида

    Подробнее

    Теория формальных систем и алгоритмов

    Теория формальных систем и алгоритмов Предварительная программа экзамена (МФТИ, осенний семестр 2017 года) Экзамен состоит из трёх частей: определения и формулировки основных теорем; доказательства фактов

    Подробнее

    Введение в математическую логику. Лекция 2

    Введение в математическую логику Лекция 2 1 С первой лекции: Что такое доказуемое математическое утверждение? Исчисления. Интегральное исчисление. Школьное исчисление уравнений. Грамматики. Тезис Гильберта

    Подробнее

    Математическая теория формальных языков - тест 12

    Главная / Алгоритмы и дискретные структуры / Математическая теория формальных языков / Тест 12 Упражнение 1:
    Номер 1
    Теорема о детерминизации
    

    Ответ:

    &nbsp(1) не переносится с конечных автоматов на автоматы с магазинной памятью&nbsp

    &nbsp(2) одинакова для конечных автоматов и автоматов с магазинной памятью&nbsp

    &nbsp(3) неприменима к автоматам с магазинной памятью&nbsp



    Номер 2
    Применение теоремы о детерминизации для конечных автоматов к автоматам с магазинной памятью

    Ответ:

    &nbsp(1) невозможно&nbsp

    &nbsp(2) возможно&nbsp

    &nbsp(3) возможно, но не имеет практического смысла&nbsp



    Номер 3
    Теорема о детерминизации для конечных автоматов и аналогичная теорема для автоматов с магазинной памятью 
    

    Ответ:

    &nbsp(1) совпадают&nbsp

    &nbsp(2) отличаются&nbsp

    &nbsp(3) абсолютно идентичны друг другу&nbsp



    Упражнение 2:
    Номер 1
    В ходе применения теоремы о детерминизации на автоматах с магазинной памятью возникает

    Ответ:

    &nbsp(1) класс языков, такой же, как и для конечных автоматов&nbsp

    &nbsp(2) класс языков, распознаваемых детерминированными автоматами с магазинной памятью&nbsp

    &nbsp(3) система формирования языков&nbsp



    Номер 2
    Класс языков, распознаваемых детерминированными автоматами с магазинной памятью

    Ответ:

    &nbsp(1) очень важен для практических приложений&nbsp

    &nbsp(2) не имеет значения для практических приложений&nbsp

    &nbsp(3) игнорируется практическими приложениями&nbsp



    Номер 3
    Формирование нового класса языков при использовании в автоматах с магазинной памятью теоремы о детерминизации

    Ответ:

    &nbsp(1) является возможным&nbsp

    &nbsp(2) не производится&nbsp

    &nbsp(3) не имеет смысла&nbsp



    Упражнение 3:
    Номер 1
    Детерминированные автоматы с магазинной памятью - это автоматы с магазинной памятью, которые 
    

    Ответ:

    &nbsp(1) ни в какой конфигурации не могут выбирать между несколькими очередными тактами&nbsp

    &nbsp(2) в любой конфигурации могут выбирать между несколькими очередными тактами&nbsp

    &nbsp(3) в любой конфигурации сами определяют все такты сразу&nbsp



    Номер 2
    Автоматы с магазинной памятью, которые ни в какой конфигурации не могут выбирать между несколькими очередными тактами - это

    Ответ:

    &nbsp(1) детерминированные автоматы с магазинной памятью&nbsp

    &nbsp(2) аддитивные автоматы с магазинной памятью&nbsp

    &nbsp(3) инъективные автоматы с магазинной памятью&nbsp



    Номер 3
    Выбор тактов детерминированными автоматами с магазинной памятью

    Ответ:

    &nbsp(1) не осуществляется&nbsp

    &nbsp(2) осуществляется&nbsp

    &nbsp(3) не имеет практического назначения&nbsp



    Упражнение 4:
    Номер 1
    Чтобы получить полезный и естественный с точки зрения практики класс языков, нужно

    Ответ:

    &nbsp(1) добавить в конец каждого слова специальный символ&nbsp

    &nbsp(2) изменить каждый символ на противоположный по значению&nbsp

    &nbsp(3) заменить каждый символ его инверсией&nbsp



    Номер 2
    Добавление в конец каждого слова языка специального символа применяется

    Ответ:

    &nbsp(1) для получения полезного и естественного класса языков&nbsp

    &nbsp(2) при формировании инверсного алфавита&nbsp

    &nbsp(3) с целью уменьшения избыточности языка&nbsp



    Номер 3
    Добавление символов к словам для получения нового класса языков

    Ответ:

    &nbsp(1) не используется из-за значительной трудоемкости&nbsp

    &nbsp(2) используется всегда&nbsp

    &nbsp(3) не имеет практического применения&nbsp



    Упражнение 5:
    Номер 1
    Маркером конца слова по своей сути является

    Ответ:

    &nbsp(1) пустое множество&nbsp

    &nbsp(2) символ&nbsp

    &nbsp(3) итерационная последовательность символов&nbsp



    Номер 2
    Маркером конца слова называют специальный символ, добавляемый

    Ответ:

    &nbsp(1) в конец каждого слова&nbsp

    &nbsp(2) в начало каждого слова&nbsp

    &nbsp(3) в середину каждого слова&nbsp



    Номер 3
    Специальный символ, добавляемый в конец каждого слова, называется

    Ответ:

    &nbsp(1) стимер&nbsp

    &nbsp(2) маркер&nbsp

    &nbsp(3) приоритет&nbsp



    Упражнение 6:
    Номер 1
    Автомат с магазинной памятью называется детерминированным, если

    Ответ:

    &nbsp(1) имеет ровно одно начальное состояние&nbsp

    &nbsp(2) все переходы этого автомата попарно несовместны&nbsp

    &nbsp(3) имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны&nbsp



    Номер 2
    Если автомат с магазинной памятью имеет ровно одно начальное состояние и все переходы этого автомата попарно несовместны, то его называют

    Ответ:

    &nbsp(1) итерационным&nbsp

    &nbsp(2) инъективным&nbsp

    &nbsp(3) детерминированным&nbsp



    Номер 3
    Детерминированный автомат с магазинной памятью имеет

    Ответ:

    &nbsp(1) одно начальное состояние&nbsp

    &nbsp(2) пару начальных состояний&nbsp

    &nbsp(3) бесконечное множество начальных состояний&nbsp



    Упражнение 7:
    Номер 1
    Детерминированным  контекстно-свободным языком является

    Ответ:

    &nbsp(1) каждый автоматный язык&nbsp

    &nbsp(2) только инъективный автоматный язык&nbsp

    &nbsp(3) единственно аддитивный автоматный язык&nbsp



    Номер 2
    Каждый автоматный язык является

    Ответ:

    &nbsp(1) детерминированным контекстно-свободным языком&nbsp

    &nbsp(2) детерминированным контекстно-ограниченным языком&nbsp

    &nbsp(3) детерминированным контекстно-обусловленным языком&nbsp



    Номер 3
    Детерминированным контекстно-свободным языком называют

    Ответ:

    &nbsp(1) любой язык&nbsp

    &nbsp(2) любой автоматный язык&nbsp

    &nbsp(3) любое непустое множество&nbsp



    Упражнение 8:
    Номер 1
    Эквивалентность автоматов с магазинной памятью доказывается с помощью

    Ответ:

    &nbsp(1) индукции по сумме избытков всех переходов&nbsp

    &nbsp(2) конъюнкции по частному избытков всех переходов&nbsp

    &nbsp(3) дизъюнкции по разности избытков всех переходов&nbsp



    Номер 2
    Индукцией по сумме избытков всех переходов доказывается

    Ответ:

    &nbsp(1) эквивалентность автоматов с магазинной памятью&nbsp

    &nbsp(2) эквипотенциальность автоматов с магазинной памятью&nbsp

    &nbsp(3) аддитивность автоматов с магазинной памятью&nbsp



    Номер 3
    При помощи метода индукции по сумме избытков всех переходов можно определить

    Ответ:

    &nbsp(1) независимость автоматов с магазинной памятью&nbsp

    &nbsp(2) перенаправленность автоматов с магазинной памятью&nbsp

    &nbsp(3) эквивалентность автоматов с магазинной памятью&nbsp



    Упражнение 9:
    Номер 1
    Детерминированый контекстно-свободный язык

    Ответ:

    &nbsp(1) является существенно неоднозначным&nbsp

    &nbsp(2) не является существенно однозначным&nbsp

    &nbsp(3) не определяется понятием однозначности&nbsp



    Номер 2
    Детерминированным контекстно-свободным языком является

    Ответ:

    &nbsp(1) дополнение детерминированного контекстно-свободного языка&nbsp

    &nbsp(2) обобщение детерминированного контекстно-свободного языка&nbsp

    &nbsp(3) итерация контекстно-свободного языка&nbsp



    Номер 3
    Дополнение детерминированного контекстно-свободного языка является

    Ответ:

    &nbsp(1) детерминированым контекстно-свободным языком&nbsp

    &nbsp(2) пустым множеством&nbsp

    &nbsp(3) символом&nbsp



    \documentclass[12pt, leqno]{article} \usepackage[T2A]{fontenc} \usepackage[utf8]{inputenc} % Кодировка входного документа; % при необходимости, вместо cp1251 % можно указать cp866 (Alt-кодировка % DOS) или koi8-r. \usepackage[english,russian]{babel} % Включение русификации, русских и % английских стилей и переносов %%\usepackage{a4} %%\usepackage{moreverb} \usepackage{amsmath,amsfonts,amsthm,amssymb,amsbsy,amstext,amscd,amsxtra,multicol} \usepackage{verbatim} \usepackage{listings} \usepackage{algorithm2e} \usepackage{tabto} %Табуляция \usepackage{tikz} %Рисование автоматов \usetikzlibrary{automata,positioning,trees} \usepackage{multicol} %Несколько колонок \usepackage{graphicx} \usepackage[colorlinks,urlcolor=blue]{hyperref} \usepackage[stable]{footmisc} \usepackage{indentfirst} % абзацный отступ после заголовка \usepackage{enumitem} %Item tricks %% \voffset-5mm %% \def\baselinestretch{1.44} \renewcommand{\theequation}{\arabic{equation}} \def\hm#1{#1\nobreak\discretionary{}{\hbox{$#1$}}{}} \newtheorem{Lemma}{Лемма} \theoremstyle{definiton} \newtheorem{Remark}{Замечание} %%\newtheorem{Def}{Определение} \newtheorem{Claim}{Утверждение} \newtheorem{Cor}{Следствие} \newtheorem{Theorem}{Теорема} \newtheorem*{known}{Теорема} \def\proofname{Доказательство} \theoremstyle{definition} \newtheorem{Def}{Определение} \theoremstyle{definition} \newtheorem{Example}{Пример} %% \newenvironment{Example} % имя окружения %% {\par\noindent{\bf Пример.}} % команды для \begin %% {\hfill$\scriptstyle\qed$} % команды для \end %\date{22 июня 2011 г.} \let\leq\leqslant \let\geq\geqslant \def\MT{\mathrm{MT}} %Обозначения ``ажуром'' \def\BB{\mathbb B} \def\CC{\mathbb C} \def\RR{\mathbb R} \def\SS{\mathbb S} \def\ZZ{\mathbb Z} \def\NN{\mathbb N} \def\FF{\mathbb F} %греческие буквы \let\epsilon\varepsilon \let\es\varnothing \let\eps\varepsilon \let\al\alpha \let\sg\sigma \let\ga\gamma \let\ph\varphi \let\om\omega \let\ld\lambda \let\Ld\Lambda \let\vk\varkappa \let\Om\Omega \def\first{\mathrm{ FIRST} } \def\follow{\mathrm{ FOLLOW} } \let\yield\Rightarrow \def\abstractname{} \def\R{{\cal R}} \def\A{{\cal A}} \def\B{{\cal B}} \def\C{{\cal C}} \def\D{{\cal D}} \let\w\omega %классы сложности \def\REG{{\mathsf{REG}}} \def\CFL{{\mathsf{CFL}}} \def\PP{{\mathsf{P}}} \def\NP{{\mathsf{NP}}} \def\NPc{{\mathsf{NP}}\text{-}{\rm c}} \def\coNP{{\rm co}\text{-}{\mathsf{NP}}} \def\DTIME{{\mathsf{DTIME}}} \def\NTIME{{\mathsf{NTIME}}} \def\HALT{{\rm{HALT}}} \def\SAT{{\rm{SAT}}} \def\3SAT{{\rm{3\text{-}SAT}}} \def\2SAT{{\rm{2\text{-}SAT}}} \def\UNSAT{{\rm{UNSAT}}} \def\LL{{\mathrm{LL}}} \def\poly{{\rm{poly}}} \newcounter{problem} \newcounter{uproblem} \newcounter{subproblem} \def\pr{\medskip\noindent\stepcounter{problem}{\bf \theproblem .\dagger$ . }\setcounter{subproblem}{0} } \def\upr{\medskip\noindent\stepcounter{uproblem}{\bf Упражнение \theuproblem . }\setcounter{subproblem}{0} } %\def\prp{\vspace{5pt}\stepcounter{problem}{\bf Задача \theproblem . } } %\def\prs{\vspace{5pt}\stepcounter{problem}{\bf \theproblem .* } \def\prsub{\medskip\noindent\stepcounter{subproblem}{\rm \thesubproblem . } } %прочее \def\quotient{\backslash\negthickspace\sim} \begin{document} \centerline{\LARGE Задание 10} \medskip \begin{center} {\Large Сложность вычислений, классы $\PP$ и $\NP$ } \end{center} \bigskip {\bf Литература: } \begin{enumerate} \item Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. \\ {\it Алгоритмы. Построение и анализ. }\\ 2-е изд. М.: Вильямс, 2005. \end{enumerate} \section{Машины Тьюринга и формальные языки} Под формальным языком $L$ мы понимаем некоторое подмножество множества всех слов над алфавитом $\Sigma$. В этой теме слова «язык» и «задача» являются синонимами, поскольку речь идёт только о задачах распознавания, то есть задач проверки принадлежности слова языку.k\times Q $ -- за такт работы машина меняет состояние, символы под каждой головкой и двигает каждую головку влево, вправо или оставляет её неподвижной. На машину могут быть наложены ограничения, например, полиномиальное время работы или полиномиальная память по входу. Среди всех лент выделена входная лента, на которой в начале работы машины написано входное слово $x$. Если машина переходит в принимающее состояние, то она останавливается и принимает входное слово. \end{Def} Будем говорить, что машина Тьюринга $M$ вычисляет функцию $M(x)$, которая равна $1$, в случае если машина $M$ на входе $x$ останавливается в принимающем состоянии, если машина $M$ на входе $x$ останавливается в не принимающем состоянии, то $M(x) = 0$, а если машина $M$ не останавливается на входе $x$, то функция $M(x)$ не определена. $$ M(x) = \begin{cases} 1, & M \text{ остановилась в принимающем состоянии на $x$;} \\ 0, & M \text{ остановилась в не принимающем состоянии на $x$;}\\ \uparrow, & M \text{ не остановилась, функция не определена на $x$.} \end{cases} $$ Машина $M$ \emph{принимает} язык $L$, если она принимает каждое слово из языка $L$, если машина $M$ принимает язык $L$ и к тому же все слова, принимаемые машиной $M$, лежат в языке $L$, то будем говорить, что машина $M$ \emph{распознаёт} $L$. Язык, распознаваемый машиной $M$ будем обозначать $L(M)$. \begin{Remark} Определение языка, распознаваемого машиной Тьюринга, при беглом взгляде кажется естественным, но на самом деле оно весьма коварно. На слова не из $L$ ограничений не накладывается, поэтому на них машина $M$ может и не останавливаться вовсе. \end{Remark} Языки, распознаваемые машинами Тьюринга, называются \emph{(рекурсивно-)перечислимыми} языками или \emph{распознаваемыми} языками. Будем говорить, что машина Тьюринга $M$ разрешает язык $L$, если она останавливается на всех входах и распознаёт язык $L$. Языки разрешимые машинами Тьюринга образуют класс \emph{рекурсивных} языков, также называемыми \emph{разрешимыми}. Аналогично определяется и недетерминированная машина Тьюринга. Если не оговорено противного, мы будем считать, что машина Тьюринга $M$ имеет одну ленту и одну головку. \bigskip \upr Покажите, что детереминированные и недетерминированные машины Тьюринга распознают один и тот же класс языков. \bigskip Поскольку машины Тьюринга имеют конечное описание, то их описание можно закодировать. Будем обозначать $M_\alpha$ машину Тьюринга, описание которой закодирована строкой $\alpha$. Мы можем просто занумеровать все возможные описания машин Тьюринга и считать, что $\alpha$ -- натуральное число. Если же это неудобно, мы можем считать, что $\alpha$ есть просто строка, содержащая описание машины Тьюринга, и если описание некорректно, то будем считать, что $M_\alpha$ -- машина Тьюринга, распознающая пустой язык. Из возможности кодирования описаний машин Тьюринга следует, что существует машина Тьюринга, которая получает на вход описание $\alpha$ и вход $x$ и проделывает работу машины $M_\alpha$ на входе $x$. Такую машину Тьюринга будем называть \emph{универсальной} и обозначать $UM$.*$ -- неразрешимая задача. \end{Example} Одна из самых распространённых неразрешимых задач -- проблема останова. Под проблемой останова понимается язык $\HALT$ состоящий из описаний всех машин Тьюринга, останавливающихся на пустом входе. \begin{Example} $$\HALT = \{ \alpha\, |\, M_\alpha(\eps) = 1 \} $$ \end{Example} \upr Докажите что язык $ \HALT $ является неразрешимый. Если доказать самостоятельно не получается, обратитесь к литературе. \bigskip Язык $L$ называется \emph{перечислимым}, если существует такая МТ $M$, которая выводит все слова из языка. МТ $M$ может вообще говоря никогда не остановится, но если слово $w$ лежит в $L$, то машина $M$ должна вывести $w$ через некоторое, быть может очень большое, число тактов. \upr Докажите, что данное здесь определение перечислимого языка согласовано с данным выше определением. \upr Докажите, что язык $\HALT$ является перечислимым. \upr Докажите, что язык $L$ является разрешимым тогда и только тогда, когда языки $L$ и $\bar L$ перечислимы.p_m L. $$ Приведём пример $\NP$-полной задачи. \begin{Example} Язык $\SAT$ состоит из всех выполнимых булевых формул $\phi$, заданных в конъюнктивной нормальной форме. $$ \SAT = \{ \phi\,|\, \exists y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 1 \} $$ \end{Example} \begin{known}[Кук, Левин] Язык $\SAT$ является $\NP$-полным. \end{known} \upr Изучить доказательство теоремы Кука-Левина. Определим язык $\3SAT$ как язык, состоящий из выполнимых булевых формул, каждый дизъюнкт которых содержит ровно три переменных. Пример такой формулы: $$ \phi = (x_1\vee x_2 \vee \neg x_3) \wedge (\neg x_4 \vee x_5 \vee x_1). $$ \prp Показать, что $\3SAT \in \NPc$ \prp Показать, что $\2SAT \in \PP$. Также нам интересен класс $\coNP$, состоящий из языков, дополнение которых лежит в $\NP$. Определим язык $\UNSAT$ как язык состоящий из невыполнимых булевых формул, заданных КНФ. То есть $$ \UNSAT = \{ \phi\,|\, \forall y_1, \ldots,y_n : \phi(y_1,\ldots,y_n ) = 0 \} $$ \upr Показать, что язык $\UNSAT$ лежит в классе $\coNP$. \end{comment} \section{О сложности вычислений} Соотношение между классами $\PP$, $\NP$ и $\NPc$ $\coNP$ представляет собой центральный вопрос сложности вычислений. Задача $\PP \stackrel{?}{\neq} \NP$ является основной в сложности вычислений и, по-видимому, безнадёжно трудной. Эта задача стала своего рода наследником теоремы Ферма, в том плане, что регулярно (хотя и не столь часто как в случае теоремы Ферма), находятся люди, которые «доказывают», что $\PP = \NP$ или обратное. Интерес к проблеме подогревается институтом Клэя, обещавшим за решение этой задачи $\$ 1\ 000\ 000$. Тем не менее, недавно была предпринята первая серьёзная попытка действительно доказать, что $\PP \neq \NP$. Так что возможно мы всё же доживём до решения этого вопроса. Сообщество верит, что $\PP \neq \NP$ и довольно многие результаты доказываются по модулю этой гипотезы. Более того, сложность этого вопроса используется на практике, в частности в криптографии. В этом курсе мы непосредственно с этим столкнёмся при изучении RSA-алгоритма шифрования. Тем не менее, то что задача лежит в $\NP$ и даже в $\NPc$ ещё вовсе не означает что её частный случай, \emph{экземпляр} трудно решить. Это означает лишь, что задача трудна только для некоторых входов. \section{Домашнее задание} Задачи из канонического задания № 8, 11-15, задача 2 из данного текста. \end{document}

    Почему машина Тьюринга распознает ровно один язык?

    Машины Тьюринга работают так, как они делают, потому что мы решили определить их так. У нас могут быть более сложные определения, но вопрос в том, послужит ли это цели, позволит ли она делать больше вещей. И, насколько нам известно, ответ - нет.

    Очень легко создавать модели машин Тьюринга, которые распознают два языка. Для языков и L 2 мы можем определить TM с двумя типами принимающего состояния: один для L 1 и один для L 2 . Можно сказать, что ТМ принимает L i, если в какой-то момент он входит в соответствующее принимающее состояние. Но он возобновит вычисления, чтобы увидеть, может ли он также перейти в другой тип принимающего состояния. И мы могли бы потребовать, чтобы это позже остановилось, или, возможно, нет. Затем вы можете построить всю теорию на таких машинах. Это будет работать и будет намного сложнее, чем мы обычно делаем.L1L1L2L2L1L1L2L2LiLi

    Чтобы ответить на утверждение Дэвида Ричерби, что « не существует механизма, с помощью которого одна машина Тьюринга могла бы принимать более одного языка », это только потому, что мы решили не рассматривать такие механизмы. Даже если вы ограничите TM очень стандартной моделью, вы можете сказать, что ввод распознается на языке когда TM останавливается в состоянии принятия с нечетным числом шагов, и это происходит в L 2, когда TM принимает с четным количеством шагов. Благодаря недетерминизму это не помешало бы ТМ распознавать оба пересекающихся языка.L1L1L2L2

    Дело в том, что для создания теории могут использоваться всевозможные варианты. Также были испробованы очень разные подходы к моделированию вычислений, такие как лямбда-исчисление, компилятивная логика, теория рекурсивных функций и многое другое.

    Всегда было показано, что ни один из них не делает ничего, что не может быть сделано нашей простой моделью, где TM распознает только один язык. До такой степени, что было предположено, что он делает все, что можно сделать. Это называется тезисом Церкви-Тьюринга . Это краеугольный камень теории вычислимости, который, насколько нам известно, определяет, какие языки распознаваемы или нет.

    Таким образом, мы могли бы также использовать простую модель, так как сложная усложнит нашу жизнь без какой-либо реальной выгоды.

    Конечно, мы иногда используем другие модели, потому что они позволяют нам лучше понять некоторые проблемы.

    1.5. Задачи - limbaje formale și proiectarea compilatoarelor

    1. Дана грамматика. Построить вывод заданной цепочки.
     
    a)      S → T | T+S | T-S T → F | F*T
     
    F → a | b
    Цепочка a-b*a+b
     
    b)     S → aSBC | abC CB → BC
     
            bB → bb bC → bc cC → cc
     
    Цепочка aaabbbccc
     
    2. Построить все сентенциальные формы для грамматики с правилами:
     
    S → A+B | B+A
    A → a
    B → b
     
    3. К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?
     

    a)  S → APA

    b)  S → aQb | ε

    P → + | -

    Q → cSc

    A → a | b

     

     
    c)  S → 1B                                                       d)  S → A | SA | SB
    B → B0 | 1                                                       A → a
    B → b
     
    4. Построить грамматику, порождающую язык :
     
    a)    L = { an bm | n, m >= 1}
    b)   L = { αcβcγc | α, β, γ - любые цепочки из a и b}
     
    c)    L = { a1 a2 ... an an ... a2 a1 | ai = 0 или 1, n >= 1}
     
    d)   L = { an bm | n ≠ m ; n, m >= 0}
     
    e)    L = { цепочки из 0 и 1 с неравным числом 0 и 1}
    f)     L = { αα | α ∈ {a,b}+}
    g)    L = { ω | ω ∈ {0,1}+ и содержит равное количество 0 и 1, причем любая
    подцепочка, взятая с левого конца, содержит единиц не меньше, чем нулей}.
    h)    L = { (a2m bm)n | m >= 1, n >= 0}
    i)      L = { a3n +1 ⊥ | n >= 1}
     
    j)     L = { a n2   | n >= 1}
     
    k)   L = { a n3 +1| n >= 1}
     
    5.  К какому типу по Хомскому относится данная грамматика? Какой язык она порождает? Каков тип языка?
     
    a)      S → a | Ba B → Bb | b
     
    c)      S → 0A1 | 01 0A → 00A1 A → 01
     
     *e) S → A | B A → aAb | 0
    B → aBbb | 1
     
    *g) S → 0S | S0 | D D → DD | 1A | ε A → 0B | ε
    B → 0A | 0
     
    *i) S → SS | A A → a | bb
     
     *k) S → aBA | ε B → bSA AA → c
     
    b)     S → Ab
    A → Aa | ba
     
    d)     S → AB AB → BA A → a
     
    B → b
     
    *f) S → 0A | 1S
    A  → 0A | 1B
    B  → 0B | 1B | ⊥
     
    *h) S → 0A | 1S | ε A → 1A | 0B B → 0S | 1B
     
     *j) S → AB⊥ A → a | cA B → bA
     
    *l) S → Ab | c A → Ba B → cS
     
    6. Эквивалентны ли грамматики с правилами :
     
      

    а)  S → AB

    и

    S → AS | SB | AB

    A → a | Aa

     

    A → a

    B → b | Bb

     

    B → b

    b)  S → aSL | aL

    и

    S → aSBc | abc

    L → Kc

     

    cB → Bc

    cK → Kc

     

    bB → bb

    K → b

     

     

    7. Построить КС-грамматику, эквивалентную грамматике с правилами:

    а)  S → aAb

     

    b)  S → AB | ABS

    aA → aaAb

     

    AB → BA

    A → ε

     

    BA → AB

     

     

    A → a

     

     

    B → b

     
    8. Построить регулярную грамматику, эквивалентную грамматике с правилами:
     
    а) S → A | AS A → a | bb
     
    b)     S → A.A
    A → B | BA B → 0 | 1
     
     
    9. Доказать, что грамматика с правилами:
     
    S → aSBC | abC CB → BC
     
    bB → bb bC → bc cC → cc
     
    порождает язык L = {an bn cn | n >= 1}. Для этого показать, что в данной грамматике
     
    1) выводится любая цепочка вида an bn cn (n >= 1) и 2) не выводятся никакие другие цепочки.
     
    10. Дана грамматика с правилами:
     
    a)  S → S0 | S1 | D0 | D1                                 b)  S → if B then S | B = E
    D → H.                                                             E → B | B + E
    H → 0 | 1 | H0 | h2                                          B → a | b
     
    Построить восходящим и нисходящим методами дерево вывода для цепочки: a) 10.1001 b) if a then b = a+b+b
     
    11. Определить тип грамматики. Описать язык, порождаемый этой грамматикой. Написать для этого языка КС-грамматику.
     
    S → P⊥
     
    P → 1P1 | 0P0 | T
    T → 021 | 120R
    R1 → 0R
    R0 → 1
    R⊥→ 1⊥
     
    12. Построить регулярную грамматику, порождающую цепочки в алфавите {a, b}, в которых символ a не встречается два раза подряд.
     
    13. Написать КС-грамматику для языка L, построить дерево вывода и левосторонний вывод для цепочки aabbbcccc.
     
    L = {a2n bm c2k | m=n+k, m>1}.
     
    14. Построить грамматику, порождающую сбалансированные относительно круглых скобок цепочки в алфавите { a, ( , ), ⊥ }. Сбалансированную цепочку α определим рекуррентно: цепочка α сбалансирована, если
    a)    α не содержит скобок,
     
    b)   α = (α1) или α= α1 α2, где α1 и α2 сбалансированы.
     

    15.

    Написать КС-грамматику, порождающую язык L, и вывод для цепочки

    aacbbbcaa в этой грамматике.

     

     

    L = {an cbm can | n, m>0}.

    16.

    Написать КС-грамматику, порождающую язык L, и вывод для цепочки

    110000111 в этой грамматике.

     

     

    L = {1n 0m 1p | n+p>m;

    n, p, m>0}.

    17.

    Дана грамматика G.

    Определить ее тип;  язык,  порождаемый этой

    грамматикой; тип языка.
     
    G:     S → 0A1 0A → 00A1
     
    A → ε
     
    18. Дан язык L = {13n+2 0n | n>=0}. Определить его тип, написать грамматику, порождающую L. Построить левосторонний и правосторонний выводы, дерево разбора для цепочки 1111111100.
     
    19. Привести пример грамматики, все правила которой имеют вид A → Bt, либо A → tB, либо A → t, для которой не существует эквивалентной регулярной грамматики.
     
    20. Написать общие алгоритмы построения по данным КС-грамматикам G1 и G2, порождающим языки L1 и L2, КС-грамматики для
    a)       L1∪L2
     
    b)      L1 * L2
    c)       L1*
     
     
     
    Замечание: L = L1 * L2 - это конкатенация языков L1 и L2, т.е.L = { αβ | α ∈ L1, β ∈ L2}; L = L1* - это итерация языка L1, т.е. объединение {ε} ∪ L1 ∪ L1*L1 ∪
    L1*L1*L1 ∪ ...
     
    21. Написать КС-грамматику для L={ωi 2 ωi+1R | i ∈ N, ωi=(i)2 - двоичное представление числа i, ωR - обращение цепочки ω}. Написать КС-грамматику для языка L* (см. задачу 20).
     
    22. Показать, что грамматика
    E → E+E | E∗E | (E) | i
     
    неоднозначна. Как описать этот же язык с помощью однозначной грамматики?
     
    23. Показать, что наличие в КС-грамматике правил вида
     
    a)       A → AA | α
    b)      A → AαA | β
    c)       A → αA | Aβ | γ
     
    где α, β , γ ∈ (VT∪VN)*, A ∈ VN, делает ее неоднозначной. Можно ли преобразовать эти правила таким образом, чтобы полученная эквивалентная грамматика была однозначной?
     
    *24. Показать, что грамматика G неоднозначна. Какой язык она порождает? Является ли этот язык однозначным?
     
    G:     S → aAc | aB B → bc
     
    A → b
     
    25.  Дана КС-грамматика G={VT, VN, P, S}. Предложить алгоритм построения множества
    X={A ∈ VN | A Þ ε}.
     
    26.           Для произвольной КС-грамматики G предложить алгоритм, определяющий, пуст ли язык L(G).
     
    27.   Написать приведенную грамматику, эквивалентную данной.
     
    a)      S → aABS | bCACd A → bAB | cSA | cCC B → bAB | cSB
     
    C → cS | c
     
    b)     S → aAB | E A → dDA | ε B → bE | f
     
    C → cAB | dSD | a D → eA
     
    E → fA | g
     
    28. Язык называется распознаваемым, если существует алгоритм, который за конечное число шагов позволяет получить ответ о принадлежности любой цепочки языку. Если число шагов зависит от длины цепочки и может быть оценено до выполнения алгоритма, язык называется легко распознаваемым. Доказать, что язык, порождаемый неукорачивающей грамматикой, легко распознаваем.
     
    29.  Доказать, что любой конечный язык, в который не входит пустая цепочка, является регулярным языком.
     
    30.    Доказать, что нециклическая КС-грамматика порождает конечный язык. Замечание: Нетерминальный символ A VN - циклический, если в
    грамматике существует вывод A Þ ξ12. КС -грамматика называется циклической, если в ней имеется хотя бы один циклический символ.
     
    31. Показать, что условие цикличности грамматики (см. задачу 30) не является достаточным условием бесконечности порождаемого ею языка.
     
    32. Доказать, что язык, порождаемый циклической приведенной КС-грамматикой, содержащей хотя бы один эффективный циклический символ, бесконечен.
     

    Замечание: Циклический символ называется эффективным, если A Þ αAβ, где |αAβ| > 1; иначе циклический символ называется фиктивным.


    информатика - распознаваемое против разрешимого

    Отказ от ответственности: я немного уточню.

    Когда машина Тьюринга (TM) получает входные данные, она может делать одно из трех:

    1. Подтвердите ввод, перейдя в состояние принятия ($ q_ {accept} $).
    2. Отклонить ввод, перейдя в состояние отклонения ($ q_ {reject} $).
    3. Продолжайте вычислять вечно. Это можно назвать «петлей».

    Если машина продолжает вычисления вечно, мы считаем, что машина отклонила строку, но делает это за бесконечное количество шагов.Таким образом, если машина принимает строку, она должна сделать это за конечное число шагов!

    Язык машины Тьюринга - это просто набор всех строк, которые принимаются машиной Тьюринга. В этом случае мы говорим, что язык распознается машиной Тьюринга. Это подводит меня к определению распознаваемого по Тьюрингу языка:

    .

    Def: язык называется распознаваемым по Тьюрингу , если его распознает какая-то машина Тьюринга.

    Теперь рассмотрим машину Тьюринга $ M $ и язык $ L $ (над входным алфавитом $ \ Sigma $), который распознается $ M $. {*} $) машина Тьюринга $ M $ решает , принять или отклонить ввод за конечное число шагов.Машина $ M $ называется решающим устройством . Языки, для которых мы можем проектировать машины Тьюринга с указанным выше свойством, называются Turing Decidable languages. В приведенном выше примере мы говорим, что $ M $ определяет $ L $. Вот определение:

    Def: язык называется разрешаемым по Тьюрингу , если некоторая машина Тьюринга решает его.

    Сохраняя простоту - язык $ L $ является разрешаемым по Тьюрингу, если какой-то решает $ M $, решает его.

    Для получения дополнительной информации вы можете обратиться к: Введение в теорию вычислений Майкла Сипсера.

    Разрешимость

    Разрешимость Пусть язык будет любым набором строк (или слов ) над заданный конечный алфавит. Алфавит может состоять из символов, которые мы обычно используются для связи, например, символы ASCII на клавиатура, включая пробелы и знаки препинания. Таким образом любая история можно рассматривать как «слово».

    Определение: Язык называется разрешимым , если есть существует метод - любой метод - для определения того, является ли данное слово принадлежит этому языку или нет.

    Рабочая гипотеза I: Разрешимость хорошо определена выше.

    Вышеприведенная гипотеза действительно кажется правдоподобной. Однако, учитывая что понятие определимости не четко определено, можно задаться вопросом, является ли ситуация разрешимости отличается. В тезисе Черча говорится, что это так, и очень глубоко. Но в этом разделе я расскажу, что можно сделать, не обращаясь к Черча, поэтому мы придерживаемся рабочей гипотезы.

    Алгоритм или рецепт для распознавания языков все, что может быть введено слово по заданному алфавиту, и что в зависимости от его ввода либо "принимает" ввод через некоторое время, либо "отклоняет" его или работает вечно, не принимая и не отклоняя его ввод.Алгоритм: останавливает , или гарантированно останавливает , если Третья возможность не возникает, т. е. если она принимает или отвергает в пределах конечное количество времени. Любой метод, который соответствует приведенному выше определению разрешимости. считается алгоритмом остановки для распознавания языков.

    Предложение: Разрешаемые языки замкнуты относительно объединения. и перекресток.

    Доказательство: Пусть L и M - языки, которые определяются алгоритмами. A и B соответственно.Чтобы решить их союз (или пересечение) просто запустите A и B параллельно для одной и той же входной строки, пока они либо принимают, либо отвергают. Строка ввода принимается, если и только если один (или оба, соответственно) принимает его, а в противном случае отклоняет.

    Предложение: Разрешаемые языки замкнуты относительно дополняемости.

    Proof: После остановки просто поменяйте местами вердикты: принять и отклонить.

    Определение: Язык называется полуразрешимым (или распознаваемый ), если существует алгоритм, который принимает данный строка тогда и только тогда, когда строка принадлежит этому языку.В случае если строка не принадлежит языку, алгоритм либо отклоняет это или бежит вечно.

    Ясно, что любой разрешимый язык узнаваем. Нам еще предстоит выяснить, существуют ли узнаваемые языки, которые не разрешимы, и существуют ли языки, которые не являются узнаваемый.

    Предложение: Узнаваемые языки закрываются объединением и перекресток.

    Доказательство: Пусть L и M - языки, распознаваемые алгоритмами. A и B соответственно.Чтобы решить их союз (или пересечение) просто запустите A и B параллельно для одной и той же входной строки. Вход строка принимается, когда ее принимает один из них (или оба, соответственно).

    Теорема: Язык разрешим тогда и только тогда, когда он и его дополнение узнаваемы.

    Доказательство: Конечно, разрешимый язык узнаваем. Более того, если язык разрешим, то значит и его дополнение, и следовательно, это дополнение узнаваемо.
    Теперь предположим, что язык L и его дополнение узнаваемы.Пусть A распознает L, а B - его дополнение. Метод решения для L получается параллельным запуском A и B на заданная строка ввода. Если A принимает строку, она принимается как член L, и в случае, если B принимает его, он отклоняется как член L. Один из этих результатов произойдет в течение конечного промежутка времени.

    Определение: Перечислитель - это алгоритм, который не принимает входных данных, и выводит возможно бесконечную последовательность строк, допускающую повторения.
    Язык называется перечислимым , если существует перечислитель выводит именно те слова, которые принадлежат этому языку.

    Теорема: Язык узнаваем тогда и только тогда, когда он перечислим.

    Проба: Предположим, что язык L узнаваем. Пусть A - алгоритм, который распознает струны, принадлежащие L. Нетрудно подобрать с перечислителем, который перечисляет все пары (w, n) с w строкой и n натуральное число.Постройте перечислитель E для L следующим образом: перечислить все пары (w, n), и для каждой такой пары запустить алгоритм A на строка w в течение n минут. Если за это время A принимает w, выведите w как часть перечисления. Если нет, просто переходите к следующей паре. Поскольку каждая строка в L будет принята A за конечный промежуток времени, он будет нумероваться E (бесконечно часто). Строки не принимаются A никогда не будет перечисляться.
    Теперь предположим, что L перечислимо. Пусть E - перечислитель для L. Определим алгоритм A следующим образом: учитывая входную строку w, запускайте E, пока она выходы w; когда это произойдет, примите.В случае, если E никогда не выводит w, алгоритм A будет работать вечно, не принимая w. Следовательно, A принимает именно те строки, которые перечислены E.

    Исходя из этого результата, слова «полуразрешимый», «узнаваемый» и «перечислимый» может использоваться взаимозаменяемо.

    Рабочая гипотеза II: Алгоритм можно представить в виде текста, т.е. как строку букв конечного алфавита, которую мы используем для коммуникация.

    Вышеприведенная гипотеза чрезвычайно правдоподобна и может быть принята за предоставляется.Любой метод распознавания строк на языке может быть помещен словами.

    Теперь возьмем за алфавит все символы, используемые для общения, и рассмотрим алгоритмы распознавания языков по этому алфавиту. Такой алгоритм может быть представлен (или задан) строкой над этим очень азбука. Поскольку любая строка может быть передана в алгоритм, одна различает те алгоритмы (представленные в виде строк), которые принимают сами, от тех, кто этого не делает.

    Теорема: Существует неузнаваемый язык.

    Проба: Рассмотрим набор L алгоритмов (для распознавания языков) - представлены в виде строк - которые сами себя не принимают. Я утверждаю, что L неузнаваемый язык. Предположим, что существует алгоритм, представлен как слово w, которое распознает L. Предположим, что w принимает сам. Тогда по определению L, w не принадлежит L. Но по определению По определению w, распознающего L, w должен быть в L. Противоречие. Теперь предположим, что w не принимает себя. Тогда по определению L, w находится в L.Но по определению w, распознающего L, w не может быть in L. Это тоже противоречие. Поскольку обе возможности относительно w принятие себя приводит к противоречию, предположению, что их существует алгоритм, распознающий, что L должно быть ложным. Следовательно, L не является узнаваемый.

    Рабочая гипотеза III: Для каждого фрагмента текста мы можем решить считается ли он алгоритмом распознавания языков или нет.

    Вышеупомянутая гипотеза чрезвычайно правдоподобна, поскольку, когда нельзя по фрагменту текста решить, алгоритм это или нет, он кажется невозможным применить этот алгоритм для распознавания конкретного язык, и, следовательно, это вообще не алгоритм.С другой стороны, один может возразить, что есть фрагменты текста, для которых это суждение позвонить, чтобы решить, достаточно ли они точны, чтобы считаться алгоритм. Однако похоже, что подобные суждения могут решаться разными способами, и каждый из этих способов ведет к работоспособная версия выдвинутой выше гипотезы.

    Теорема: Существует язык, который узнаваем, но не разрешим.

    Проба: Рассмотрим множество алгоритмов M (для распознавания языков) - представлены в виде строк - которые принимают сами себя.Я утверждаю, что язык M узнаваем, но не разрешим. По первому требованию построить алгоритм, распознающий M следующим образом: при представлении строка w, проверьте, является ли w алгоритмом распознавания языков или нет. Если нет, откажитесь. Если это так, запустите алгоритм, представленный буквой w, на строка w. Принять именно тогда, когда w примет. Этот алгоритм явно признает М.
    Что касается второго утверждения, предположим, что M разрешима. Тогда также его дополнение было бы разрешимо, как и пересечение его дополнять языком все алгоритмы распознавания языков.Но это пересечение в точности L, язык, показанный как неузнаваемым, а значит, и неразрешимым в предыдущем доказательстве. Это противоречие показывает, что M неразрешима.


    Следствие (проблема принятия ): Язык AP всех строк (v, w), где v - алгоритм, принимающий слово w узнаваемо, но неразрешимо.

    Доказательство: То, что точка доступа узнаваема, отображается так же, как и для язык M выше. Постройте алгоритм, распознающий AP как следующим образом: при представлении строки (v, w) проверьте, является ли v алгоритм распознавания языков или нет.Если нет, откажитесь. Если да, запустите алгоритм, представленный буквой v в строке w. Принять ровно тогда, когда w принимает. Этот алгоритм четко распознает AP.
    То, что AP неразрешимо, следует за уменьшением до неразрешимость языка M выше. Предположим, у нас будет алгоритм определения AP. Затем алгоритм определения того, является ли строка w находится в M будет просто состоять из подачи строки (w, w) в алгоритм определения AP. Поскольку M неразрешима, такой алгоритм не может существует, а значит, и AP должна быть неразрешимой.

    Примечание: Проблема приемки, сформулированная выше, страдает от двусмысленность: может оказаться, что данная строка может быть проанализирована в нескольких разными способами как пара (v, w). Это происходит, если в v или w есть запятые. Решение этой проблемы - написать любую запятую "," в v или w как "\" и любая обратная косая черта "\" как "\\". Согласно этой конвенции запятая, отделяющая v от w, однозначно узнаваема как таковая.

    Мы говорим, что алгоритм останавливает на входе w, если он принимает или отвергает слово w (через конечный промежуток времени).Алгоритм останавливает , если он останавливается при каждом вводе.

    Следствие (проблема остановки ): Язык HP всех строк (v, w), где v - остановка алгоритма. на входе w неразрешима.

    Доказательство: редукцией до неразрешимости AP. Предположим, у нас есть алгоритм определения HP. Тогда алгоритм решение AP получается следующим образом. Подайте входную строку в HP. Если он отклонен, откажитесь. В противном случае входная строка должна иметь form (v, w), в котором v - алгоритм, останавливающийся на входе w.Так что запустите v на w и проверьте, принято ли w. Об этом узнают в конечное количество времени, потому что уже известно, что v остановится.

    Домашнее задание: Пусть K будет набор алгоритмов остановки (для распознающие языки) - представленные в виде строк - которые принимают самих себя. Покажите, что K - неразрешимый язык.

    Домашнее задание: Докажите, что язык H всех алгоритмов остановки неразрешима, т.е. невозможно решить, является ли данный алгоритм останавливается на всех входах.


    3.1 Язык и значение - общение в реальном мире

    Цели обучения

    1. Объясните, как смысловой треугольник описывает символическую природу языка.
    2. Различайте значение и оттенок.
    3. Обсудите функцию правил языка.
    4. Опишите процесс овладения языком.

    Отношения между языком и значением не являются однозначными. Одна из причин таких сложных взаимоотношений - безграничность современных языковых систем, таких как английский (Crystal, 2005).Язык продуктивен в том смысле, что существует бесконечное количество высказываний, которые мы можем сделать, соединяя существующие слова новыми способами. Кроме того, словарный запас языка неограничен, так как новые слова придумываются ежедневно. Конечно, слова - не единственное, что нам нужно для общения, и хотя вербальное и невербальное общение тесно связано с точки зрения того, как мы придаем смысл, невербальное общение не является продуктивным и безграничным. Хотя мы можем сделать всего несколько сотен физических знаков, в английском языке у нас есть около миллиона слов.Итак, при всей этой возможности, как общение порождает смысл?

    Как вы помните, «создание смысла» было центральной частью определения коммуникации, которое мы узнали ранее. Мы достигаем смысла через взаимодействие между нашей нервной и сенсорной системами и некоторыми внешними стимулами. Именно здесь, между теми моделями коммуникации, которые мы обсуждали ранее, обозначенными как кодирование и декодирование, генерируется смысл по мере интерпретации сенсорной информации. Непрямые, а иногда и сложные отношения между языком и смыслом могут привести к путанице, разочарованию или даже юмору.Мы можем даже немного испытать все три, когда остановимся и задумаемся о том, что существует около двадцати пяти определений, которые говорят нам значение слова , означающего ! (Crystal, 2005) Поскольку язык и символы являются основным средством нашего общения, важно, чтобы мы не воспринимали компоненты нашего вербального общения как должное.

    Язык символичен

    Наша языковая система в основном состоит из символов. Символ - это что-то, что заменяет или представляет что-то еще.Символы могут передаваться устно (произнося слово , привет, ), письменно (складывая буквы H-E-L-L-O вместе) или невербально (размахивая рукой взад и вперед). В любом случае символы, которые мы используем, заменяют что-то еще, например, физический объект или идею; они фактически не соответствуют предмету, на который имеется прямая ссылка. В отличие от иероглифов в Древнем Египте, которые часто имели буквальную связь между письменным символом и объектом, на который ссылаются, символы, используемые в современных языках, не похожи на объект или идею, к которым они относятся.

    Используемые нами символы образуют языковые системы или коды. Коды - это культурно согласованные и постоянно меняющиеся системы символов, которые помогают нам организовывать, понимать и генерировать смысл (Leeds-Hurwitz, 1993). В мире используется около 6000 языковых кодов, и около 40 процентов из них (2400) только разговорные и не имеют письменной версии (Crystal, 2005). Помните, что на протяжении большей части истории человечества устное слово и невербальное общение были основными средствами общения.Даже в языках с письменным компонентом не было широко распространенной грамотности или способности читать и писать чуть более ста лет назад.

    Символический характер нашего общения уникален для людей. Поскольку слова, которые мы используем, не обязательно должны напрямую соответствовать «вещи» в нашей «реальности», мы можем общаться в абстракциях. Это свойство языка называется смещением и конкретно относится к нашей способности говорить о событиях, которые удалены в пространстве или времени от говорящего и ситуации (Crystal, 2005).Животные общаются, но гораздо проще, это всего лишь реакция на раздражитель. Кроме того, общение животных очень ограничено, и ему не хватает продуктивного качества языка, о котором мы говорили ранее.

    Хотя животные действительно общаются определенным образом, способность людей использовать символы для общения о вещах за пределами нашего непосредственного окружения и опыта уникальна.

    Джошуа Аллен - Барк - CC BY-NC-ND 2.0.

    Как я отмечал в главе 1 «Введение в коммуникативные исследования», самое раннее человеческое устное общение не было очень символическим или абстрактным, поскольку оно, вероятно, имитировало звуки животных и природы.Такая простая форма общения сохранялась в течение тысяч лет, но по мере того, как позже люди обратились к оседлому сельскому хозяйству и население росло, вещи должны были быть более различимыми. Требовалось больше терминов (символов), чтобы учесть все большее количество таких вещей, как инструменты и идеи, такие как севооборот, которые возникли в результате новых знаний и опыта в области сельского хозяйства и приручения животных. В то время не было письменных символов, но объекты часто использовались для обозначения других объектов; например, фермер мог хранить камешек в коробке, чтобы представить каждого цыпленка, которым он владел.По мере того, как дальнейшие достижения усложнили отслеживание объектов, представляющих объекты, более абстрактные символы и более поздние письменные слова смогли заменить идею или объект. Несмотря на то, что эти переходы произошли много тысяч лет назад, мы можем проследить некоторые слова, которые мы все еще используем сегодня, до их гораздо более прямого и гораздо менее абстрактного происхождения.

    Например, слово вычислить происходит от латинского слова исчисление , что означает «камешек.«Но какое отношение имеет камешек к расчетам? Галька использовалась для вычислений очень давно, еще до того, как мы разработали устную или письменную систему счисления (Hayakawa & Hayakawa, 1990). Как я отмечал ранее, фермер мог хранить в ящике по камешку на каждую свою кур. Каждый камешек представлял одну курицу, а это означало, что каждый символ (камешек) имел прямую связь с другой вещью в мире (своей курицей). Эта система позволяла фермеру следить за своим скотом. Он мог периодически проверять, что каждому камушку соответствует курица.Если бы было несоответствие, он бы знал, что курица была потеряна, украдена или убита. Позже были разработаны символы, которые немного упростили учет. Вместо того, чтобы вести учет коробок с галькой, фермер мог записать такой символ, как слово , пять, , или цифру, 15, , которые могли заменять пять или пятнадцать камешков. Это демонстрирует, как эволюционировали наши символы и что некоторые из них до сих пор несут с собой эту древнюю историю, хотя мы и не подозреваем об этом. Хотя эта эволюция в некотором смысле облегчила общение, она также открыла пространство для недопонимания, поскольку отношения между символами и объектами или идеями, которые они представляли, стали менее прямолинейными.Хотя корень вычислить означает «камешек», слово вычислить сегодня имеет по крайней мере шесть общих определений.

    Треугольник смысла

    Смысловой треугольник - это модель коммуникации, которая указывает на отношения между мыслью, символом и референтом и подчеркивает косвенную связь между символом и референтом (Richards & Ogden, 1923). Как вы можете видеть на рис. 3.1 «Треугольник смысла», мысль - это концепция или идея, на которые ссылается человек.Символ - это слово, представляющее мысль, а референт - это объект или идея, к которым относится символ. Эта модель полезна для нас как коммуникаторов, потому что, когда мы осознаем косвенную связь между символами и референтами, мы осознаем, как часто возникают недопонимания, как показывает следующий пример: Джаспер и Эбби думали о завести новую собаку. Итак, у каждого из них похожие мысли. Каждый из них использует один и тот же символ, слово собака , чтобы сообщить о своих мыслях.Однако их референты разные. Джаспер думает о маленькой собаке, как о таксе, а Эбби думает об австралийской овчарке. Поскольку слово собака не относится к одному конкретному объекту в нашей реальности, они могут иметь ту же мысль и использовать один и тот же символ, но в конечном итоге в неловком моменте, когда они добираются до убежища и падают. влюблены в своих соответственных референтов только для того, чтобы узнать, что другой человек не имел в виду то же самое.

    Рисунок 3.1 Треугольник значения

    Источник: по материалам Ivor A. Richards и Charles K. Ogden, The Meaning of Meaning (Лондон: Кеган, Пол, Тренч, Табнер, 1923).

    Зная об этой косвенной связи между символом и референтом, мы можем попытаться компенсировать ее, получив разъяснения. Здесь может быть полезно кое-что из того, что мы узнали в главе 2 «Коммуникация и восприятие» о проверке восприятия. Эбби могла бы спросить Джаспера: «Какую собаку ты имеешь в виду?» Этот вопрос позволил бы Джасперу описать своего референта, что обеспечило бы более общее понимание.Если Джаспер ответит: «Ну, мне нравятся короткошерстные собаки. И нам нужна собака, которая будет хорошо работать в квартире », - тогда еще есть целый ряд референтов. Эбби могла бы задать вопросы для уточнения, например: «Похоже, вы говорите, что собака поменьше могла бы быть лучше. Это правильно?" Достижение общего понимания может быть трудным, даже когда мы определяем наши символы и описываем наши референты.

    Определения

    Определения помогают нам сузить значение определенных символов, что также сужает возможные референции символа.Они также предоставляют больше слов (символов), для которых мы должны определить референт. Если понятие абстрактное и слова, используемые для его определения, также абстрактны, то определение может быть бесполезным. Вы когда-нибудь попадали в словесный лабиринт, когда ищите незнакомое слово и обнаруживаете, что определение содержит больше незнакомых слов? Хотя это может расстраивать, определения действительно служат цели.

    Слова имеют денотативное и коннотативное значения. Обозначение относится к определениям, которые принимаются языковой группой в целом, или к словарному определению слова.Например, обозначение слова ковбой - это мужчина, который ухаживает за скотом. Другое обозначение - безрассудный и / или независимый человек. Более абстрактное слово, например изменить , будет труднее понять из-за множества обозначений. Поскольку оба слова cowboy и change имеют несколько значений, они считаются многозначными словами. Однозначные слова имеют только одно использование в языке, что упрощает их обозначение. Специализированные академические или научные слова, такие как моносемический , часто являются однозначными, но обычно используется меньше однозначных слов, например, носовой платок .Как вы можете догадаться, основываясь на нашем обсуждении сложности языка, количество однозначных слов намного меньше, чем многозначных слов.

    Под коннотацией понимаются определения, основанные на ассоциациях людей со словом, основанных на эмоциях или опыте. Возвращаясь к нашим предыдущим словам, изменение может иметь положительные или отрицательные коннотации в зависимости от опыта человека. Человек, который только что закончил долгосрочные отношения, может думать об изменениях как о хорошем или плохом, в зависимости от того, что он думает о своем бывшем партнере.Даже однозначные слова, такие как носовой платок , которые имеют только одно значение, могут иметь несколько значений. Носовой платок может вызвать в воображении мысли об изящных южных красавицах или отвратительных соплях. Многозначное слово, такое как cowboy , имеет множество коннотаций, и философы языка исследовали, как коннотации выходят за пределы одного или двух экспериментальных или эмоциональных значений слова, чтобы составить культурные мифы (Barthes, 1972). Cowboy , например, связывает границу и западную историю Соединенных Штатов, с которой связаны мифологии, которые помогают формировать нарратив нации.Marlboro Man - неизменный рекламный символ, который использует коннотации ковбоя для привлечения клиентов. В то время как люди, которые выросли со скотом или имеют семью на этом ранчо, могут иметь очень специфическое значение слова ковбой , основанное на личном опыте, на коннотации других людей может в большей степени влиять популярная культурная символика, подобная той, что наблюдается в вестернах.

    Язык изучается

    Как мы только что узнали, отношения между символами, составляющими наш язык, и их референтами произвольны, а это означает, что они не имеют значения, пока мы не приписываем его им.Чтобы эффективно использовать языковую систему, мы должны со временем узнать, какие символы связаны с какими референтами, поскольку мы не можем просто сказать, глядя на символ. Как и я, вы, вероятно, узнали, что означает слово яблоко , посмотрев на буквы A-P-P-L-E и изображение яблока и попросив учителя или воспитателя помочь вам произнести буквы, пока вы не произнесете все слово. Со временем мы связали эту комбинацию букв с изображением восхитительного красного яблока, и нам больше не приходилось озвучивать каждую букву.Это преднамеренный процесс, который в данный момент может показаться медленным, но, как мы увидим дальше, наша способность овладевать языком на самом деле поразительна. Однако мы не просто учили отдельные слова и их значения; мы также выучили правила грамматики, которые помогают нам складывать эти слова в осмысленные предложения.

    Мы изучаем правила языка, когда учимся говорить и читать.

    Энди Робертс - Чтение - CC BY 2.0.

    Правила языка

    Любая языковая система должна иметь правила, делающие ее доступной для изучения и использования.Грамматика относится к правилам, которые определяют, как слова используются для составления фраз и предложений. Кто-то наверняка поймет, что вы подразумеваете под вопросом "Где пульт?" Но "Пульт управления где?" может быть непонятным или, по крайней мере, запутанным (Crystal, 2005). Знание правил грамматики важно для того, чтобы уметь писать и говорить так, чтобы вас понимали, но знания этих правил недостаточно, чтобы стать эффективным коммуникатором. Как мы узнаем позже, творчество и игра также играют роль в эффективном вербальном общении.Несмотря на то, что учителя давно навязывают идею о том, что существуют правильные и неправильные способы писать и произносить слова, на самом деле нет ничего изначально правильного или неправильного в том, что мы делаем индивидуальный выбор в использовании нашего языка. Скорее, это наше коллективное соглашение, которое дает силу правилам, регулирующим язык.

    Некоторые лингвисты считали правила языка довольно жесткими и ограничивающими с точки зрения возможных значений, которые мы можем извлечь из слов и предложений, созданных изнутри этой системы (de Saussure, 1974).Другие считали эти правила более открытыми и гибкими, позволяющими человеку делать выбор для определения смысла (Eco, 1976). Третьи утверждали, что настоящего смысла нет и что возможности смысла безграничны (Derrida, 1978). Для наших целей в этой главе мы возьмем среднюю перспективу, которая допускает возможность индивидуального выбора, но все же признает, что существует система правил и логики, которая направляет наше принятие решений.

    Оглядываясь назад на наше обсуждение коннотации, мы можем увидеть, как люди играют роль в том, как связаны значение и язык, поскольку каждый из нас привносит свои собственные эмоциональные и эмпирические ассоциации со словом, которые часто более значимы, чем определение из словаря.Кроме того, у нас есть довольно много места для творчества, игры и сопротивления с используемыми символами. У вас когда-нибудь был секретный код с другом, который знали только вы? Это может позволить вам использовать кодовое слово в общественном месте, чтобы донести смысл до другого человека, который «в курсе», и никто не поймет сообщение. Тот факт, что вы можете взять слово, придать ему другое значение, попросить кого-то согласиться с этим значением, а затем использовать это слово по-своему, ясно показывает, что значение заключается в людях, а не в словах.Как мы узнаем позже, многие сленговые слова возникли из-за того, что люди хотели скрытно поговорить на определенные темы, такие как наркотики или секс, чтобы посторонние не зацепились за это.

    Приобретение языка

    Приобретение языка относится к процессу, с помощью которого мы учимся понимать, производить и использовать слова для общения в рамках данной языковой группы. На то, как мы изучаем язык, влияет множество факторов. Мы знаем, что изучение языка - это не только изучение слов. Мы должны научиться правильно связывать слова с тем, что они означают в данном контексте, и уметь упорядочивать слова таким образом, в рамках правил грамматики для языкового кода, который мы используем, чтобы другие люди могли поймите нас (Хаякава и Хаякава, 1990).Как будто этого показалось недостаточно, чтобы научиться, мы также должны изучить различные разговорные шаблоны, которым мы регулярно, но часто неосознанно следуем, чтобы наши взаимодействия были гладкими и успешными. Краткий обзор овладения языком от рождения до взрослой жизни предлагает нам взглянуть на удивительные и все еще несколько загадочные отношения между нашим мозгом, глазами, ушами, голосом и другими физиологическими элементами (Crystal, 2005). Что касается усвоения языка, на самом деле существует большая разница между людьми из-за физических и контекстных различий, но этот обзор предполагает «типичное развитие».”

    Многое изучается в течение первого года жизни, поскольку развитие мозга ускоряется, а чувства сфокусированы и настроены. Лица, осуществляющие первичный уход, почти инстинктивно склоняются к тому, чтобы с рождения прививать младенцам разговорные способности. Практически любой, кто проводил время с младенцем на этом этапе быстрого развития, может подтвердить, что есть принуждение к взаимодействию с ребенком, что обычно доставляет удовольствие взрослым и младенцам. Это принуждение не является случайным или случайным, и мы ошибаемся, полагая, что наше общение бесполезно или просто для развлечения.Мы также ошибаемся, полагая, что овладение языком начинается только после того, как ребенок произнесет свои первые слова. К тому времени, когда это происходит, младенцы уже многое узнают благодаря наблюдению и практике о нашем вербальном общении и моделях взаимодействия. Эти ключевые события включают следующее:

    • 2–4 мес. Младенцы могут реагировать на разные тона голоса (сердитый, успокаивающий или игривый).
    • 6 мес. Младенцы могут ассоциировать некоторые слова, например bye-bye , с соответствующим поведением, и они начинают «лепетать», что на самом деле является практикой для более разборчивой речи в будущем.
    • 8–10 мес. Младенцы узнают, что указание может привлекать или направлять внимание, и начинают следить за разговорами взрослых, переводя зрительный контакт с одного говорящего на другого.
    • 1 год. Младенцы распознают отдельные слова (имена людей, ) и основные ритуалы вербального взаимодействия, такие как вопрос-пауза-ответ и различные приветствия. Незадолго до или после этого времени младенцы начинают использовать «мелодические высказывания», отражающие разнообразие высоты тона и тона в различных вербальных взаимодействиях, таких как вопросы, приветствия или пожелания.

    К тому времени, когда детям исполняется год, они выучивают многие модели речи, хотя еще не могут использовать их в узнаваемом использовании.

    Освоение языка после двухлетнего возраста кажется медленным по сравнению с темпами развития в течение первого года или около того. К концу первого года жизни младенцы усваивают большинство основных фонетических компонентов, необходимых для речи. Второй год представляет собой время интенсивной практики - словесных проб и ошибок.С трех до пяти мы продолжаем развивать нашу способность к произношению, которая к подростковому возрасту развивается достаточно, чтобы позволить нам участвовать в повседневном общении. Конечно, наш выразительный репертуар, включая манеру речи и словарный запас, который мы используем, продолжает развиваться. Выбор человека в жизни и карьере в значительной степени определяет, насколько будет происходить его дальнейшее развитие. Но приобретенные нами языковые способности могут уменьшиться или исчезнуть в результате болезни или травмы. Кроме того, если такие вещи происходят в раннем возрасте или до рождения, процесс овладения языком может быть совершенно другим.Препятствия на пути к речи и овладению языком являются обычным явлением и являются областью родственной, но отдельной области исследования, часто размещаемой в отделах коммуникативных наук и расстройств. В блоке «Как стать реальным» обсуждается эта область обучения и связанные с ней карьеры.

    «Реальность»

    Коммуникационные науки и расстройства

    Область коммуникативных наук и расстройств включает карьерный рост в аудиологии и речевой патологии - здесь мы сосредоточимся на последней.Люди, работающие в этой области, могут работать в школах, больницах, в частной практике или в академических кругах в качестве исследователей и профессоров. Речевые и языковые расстройства затрагивают миллионы людей. От шести до восьми миллионов человек в Соединенных Штатах имеют какие-либо языковые нарушения, начиная от заикания и заканчивая отсутствием понимания языка и отсутствием языкового выражения. Патологи речевого языка могут работать с детьми, которые продемонстрировали заметную медлительность или разрыв в овладении языком, или взрослыми, которые недавно потеряли языковые способности из-за инсульта или какой-либо другой травмы или заболевания.Патологи речи часто диагностируют и лечат языковые расстройства в составе команды, в которую могут входить учителя, врачи, социальные работники и другие. Прогнозируется, что карьерные перспективы будут очень хорошими в следующие восемь лет, поскольку бэби-бумеры достигнут возраста, в котором развиваются возрастные нарушения слуха и речи, поскольку достижения медицины увеличивают выживаемость недоношенных детей, жертв инсульта и травм, а также по мере продолжения образования в школах. расти. Патологи-речевые патологи часто получают ученые степени, проходят полный клинический опыт и сдают тесты для получения различных сертификатов и лицензий.Чтобы добиться успеха в этой области, люди должны обладать хорошими навыками межличностного общения для работы с множеством клиентов и других поставщиков услуг, интеллектуальными способностями выше среднего (особенно в области науки) и отличными устными и письменными коммуникативными навыками. Типичная заработная плата составляет от 58 000 долларов в год для лиц, работающих в начальных школах, до 70 000 долларов для тех, кто работает в медицинских учреждениях.

    1. Какие конкретные коммуникативные навыки, по вашему мнению, будут важны для патолога речи и почему?
    2. Девиз Американской ассоциации говорящих, говорящих и слышащих: «Сделать эффективное общение правом человека, доступным и достижимым для всех.«Как этот девиз соотносится с нашим обсуждением этики общения до сих пор? Что делают патологи речи в соответствии с этим девизом?

    Основные выводы

    • Треугольник значения - это модель коммуникации, которая указывает на отношения между мыслью, символом и референтом и подчеркивает косвенную связь между символом и референтом. Модель объясняет, как для любого данного символа может быть много разных референтов, что может привести к недопониманию.
    • Обозначение относится к согласованному или словарному определению слова. Connotation относится к определениям, основанным на ассоциациях людей со словом, основанных на эмоциях или опыте.
    • Правила языка помогают сделать его доступным для изучения и использования. Хотя правила ограничивают некоторые виды использования языка, они по-прежнему допускают возможность творчества и игры.
    • Приобретение языка относится к процессу, с помощью которого мы учимся понимать, производить и использовать слова для общения в данной языковой группе.Этот процесс происходит с поразительной скоростью в течение первых двух лет жизни, и мы получаем всю языковую информацию, необходимую для участия в повседневных разговорах, при условии нормального развития, к нашему раннему подростковому возрасту.

    Упражнения

    1. Проследите историю слова (его этимологию), как мы это делали с , вычислите ранее в этой главе. Обсудите, как значение слова (символа) изменилось по мере того, как оно ускользнуло от своего первоначального значения. Два интересных слова, которые нужно отследить, - это опасность и фальшивый .
    2. Примените треугольник значений к недавнему обмену сообщениями, в котором разные ссылки привели к недопониманию. Что вы могли сделать, чтобы предотвратить или исправить недоразумение?
    3. Придумайте несколько слов, которые имеют для вас сильную коннотацию. Чем ваш оттенок отличается от значения? Чем ваш оттенок может отличаться от другого человека?

    Список литературы

    Барт, Р., Мифологии, (Нью-Йорк, Нью-Йорк: Хилл и Ван, 1972).

    Кристал, Д., Как работает язык: как младенцы бормочут, слова меняют значение и языки живут или умирают (Вудсток, Нью-Йорк: Overlook Press, 2005), 8–9.

    де Соссюр, Ф., Курс общего языкознания , пер. Уэйд Баскин (Лондон: Фонтана / Коллинз, 1974).

    Derrida, J., Writing and Difference , trans. Алан Басс (Лондон: Рутледж, 1978).

    Эко, У., Теория семиотики (Блумингтон, Индиана: издательство Индианского университета, 1976).

    Хаякава С. И. и Алан Р. Хаякава, Язык в мышлении и действии, , 5-е изд. (Сан-Диего, Калифорния: Harcourt Brace, 1990), 87.

    Leeds-Hurwitz, W., Semiotics and Communication: Signs, Codes, Cultures (Hillsdale, NJ: Lawrence Erlbaum Associates, 1993), 53.

    Ричардс И. А. и Чарльз К. Огден, Значение смысла (Лондон: Кеган, Пол, Тренч, Табнер, 1923).

    Вопросы и ответы по теории автоматов для опытных

    | M - это DFA, и M распознает ввод w}.
    Заполните бланк:
    Rec-DFA ___________
    a) Неразрешимый
    b) Разрешаемый
    c) Не конечный
    d) Ни один из упомянутых. следующая лемма, которая утверждает, что ДКА, распознающая вход w, разрешима.

    5. Какие из следующих полуразрешимых?
    a) Пустой-DFA
    b) Rec-NFA
    c) Бесконечный-DFA
    d) Все упомянутые
    Просмотреть ответ

    Ответ: d
    Объяснение: Все являются свойствами обычных языков и все являются разрешимыми языками.

    6. Язык, принятый машиной Тьюринга, называется ____________
    a) Рекурсивное перечислимое
    b) Рекурсивное перечисляемое
    c) Рекурсивное перечисляемое и рекурсивное
    d) Ни одно из упомянутых
    Просмотреть ответ

    Ответ: c
    Объяснение: Принятый язык машины Тьюринга называются рекурсивно перечислимыми (RE), а подмножество языков RE, которые принимаются машиной Тьюринга, которая всегда останавливается, называют рекурсивными.

    7. Разрешаемый может быть взят как синоним:
    a) рекурсивный
    b) нерекурсивный
    c) распознаваемый
    d) ни один из упомянутых
    Просмотреть ответ

    Ответ: a
    Объяснение: Мы можем называть языки как ' рекурсивный », а проблемы - как« разрешимые ».Если язык не рекурсивен, то мы называем проблему, выражаемую этим языком, неразрешимой.

    8. Задачи, у которых нет алгоритма, независимо от того, принимаются ли они машиной Тьюринга, которая не может остановиться на каком-либо входе, называются: упомянутый
    Посмотреть ответ

    Ответ: b
    Объяснение: Проблемы, которые могут быть решены машиной Тьюринга, можно разделить на два класса:
    a) Те, у которых есть алгоритм
    b) Непреодолимые проблемы: Те, которые решаются только с помощью машина Тьюринга, которая может работать вечно на входных данных, которые они не принимают.

    9. Алгоритм называется эффективным, если он выполняется за ____________ раз на последовательном компьютере.
    a) полиномиальный
    b) неполиномиальный
    c) логарифмический
    d) ничего из упомянутого
    Просмотреть ответ

    Ответ: a
    Объяснение: Пример: время выполнения эффективных алгоритмов
    O (n), O (nlogn), O ( n 3 log2 n )
    Время выполнения неэффективных алгоритмов
    O (2 n ), O (n!)

    10. Проблема называется __________, если для нее есть эффективный алгоритм.
    a) послушный
    b) труднопреодолимый
    c) вычислительный
    d) ни один из упомянутых
    Посмотреть ответ

    Ответ: a
    Объяснение: проблема называется трудноразрешимой, если существует эффективный (т. Е. Полиномиальное время) алгоритм, который ее решает. Проблема называется неразрешимой, если не существует эффективного алгоритма, который ее решает.

    11. Формальный язык является рекурсивным, если:
    a) существует полная машина Тьюринга
    b) машина Тьюринга, которая останавливается для каждого ввода
    c) машина Тьюринга отклоняет, если ввод не принадлежит языку
    d) все упомянуто
    Просмотреть ответ

    Ответ: d
    Объяснение: Формальный язык называется рекурсивным, если он является рекурсивным подмножеством множества всех возможных конечных последовательностей по алфавиту языка.

    12. Рекурсивные языки также известны как:
    a) разрешимый
    b) неразрешимый
    c) иногда разрешимый
    d) ни один из упомянутых
    Просмотреть ответ

    Ответ: a
    Объяснение: язык является рекурсивным, если существует тьюринг. машина так, что она останавливается, т.е. принимает, если ввод принадлежит языку, иначе отклоняет. Его лучше назвать разрешимым языком Тьюринга.

    13. Класс рекурсивного языка известен как:
    a) R
    b) RC
    c) RL
    d) Все упомянутые
    Просмотреть ответ

    Ответ: a
    Объяснение: R - это набор всех рекурсивных языков. , класс задач решения, решаемых машинами Тьюринга.Хотя R также используется для класса RP.

    14. Что из следующего не входило в иерархию Хомского?
    a) Контекстно-зависимая грамматика
    b) Неограниченная грамматика
    c) Рекурсивная грамматика
    d) Ни один из упомянутых
    Просмотреть ответ

    Ответ: c
    Объяснение: Все рекурсивные языки рекурсивно перечислимы. Все обычные, контекстно-зависимые и контекстно-зависимые языки рекурсивны.

    Sanfoundry Global Education & Learning Series - Теория автоматов.
    Чтобы практиковать все области теории автоматов для опытных людей, представляет собой полный набор из 1000+ вопросов и ответов с множественным выбором .

    Примите участие в конкурсе сертификации Sanfoundry, чтобы получить бесплатную Почетную грамоту. Присоединяйтесь к нашим социальным сетям ниже и будьте в курсе последних конкурсов, видео, стажировок и вакансий!

    по классификации Хомского | Формальные языки и компиляторы

    В этой главе вы изучите четыре класса формальных языков, представленных Ноамом Хомским.

    Самая известная классификация грамматик и языков, представленная Ноамом Хомским, разделена на четыре класса:

    • Рекурсивно перечисляемые грамматики - распознаваемые машиной Тьюринга
    • Контекстно-зависимые грамматики - распознаваемые линейно ограниченный автомат
    • Контекстно-свободные грамматики - распознаваемые автоматом выталкивания
    • Регулярные грамматики - распознаваемые конечным автоматом

    Интересно…

    , американский лингвист, философ, когнитивист и общественный деятель.Хомский хорошо известен в академическом и научном сообществе как один из отцов современной лингвистики и крупный деятель аналитической философии.

    0 - Рекурсивно перечисляемая грамматика

    Грамматики типа 0 (неограниченные грамматики) включают все формальные грамматики. Они генерируют в точности все языки, распознаваемые машиной Тьюринга. Эти языки также известны как языки с рекурсивным перечислением. Обратите внимание, что это отличается от рекурсивных языков, которые могут быть решены постоянно останавливающейся машиной Тьюринга.

    Грамматики класса 0 слишком общие, чтобы описывать синтаксис языков программирования и естественных языков.

    1 - Контекстно-зависимые грамматики

    Грамматики типа 1 генерируют контекстно-зависимые языки. Эти грамматики имеют правила вида α A β → α γ β с нетерминалом A и строками терминалов и нетерминалов α, β и γ. Строки α и β могут быть пустыми, но строка γ должна быть непустой. Языки, описываемые этими грамматиками, - это в точности все языки, которые могут быть распознаны линейным ограниченным автоматом.

    Пример:

    AB → CDB
    AB → CdEB
    ABcd → abCDBcd
    B → b

    2 –Граммы без контекста

    900–2

    0 без контекста. генерировать контекстно-свободные языки. Они определены правилами вида A → γ, где

    A - нетерминал, а γ - цепочка терминалов и нетерминалов. Эти языки - в точности все языки, которые могут быть распознаны недетерминированным автоматом выталкивания вниз.Контекстно-свободные языки являются теоретической основой синтаксиса большинства языков программирования.

    Пример:

    A → aBc

    3 –Регулярные грамматики

    Грамматики типа 3 генерируют регулярные языки. Такая грамматика ограничивает свои правила одним нетерминалом в левой части и правой частью, состоящей из одного терминала, за которым может следовать (или которому предшествует, но не оба в одной грамматике) один нетерминал.Правило S → ε также разрешено здесь, если S не появляется справа от любого правила. Эти языки - в точности все языки, которые могут быть определены конечным автоматом. Кроме того, это семейство формальных языков можно получить с помощью регулярных выражений. Обычные языки обычно используются для определения шаблонов поиска и лексической структуры языков программирования.
    Пример:

    A → ε
    A → a
    A → abc
    A → B
    A → abcB

    L… 1 и L 2 являются обычными, также являются регулярными следующие языки:

    L 1 ∪ L 2
    L 1 ∩ L 2
    306
    L * L 2 = {xy: x ∈ L 1 ∧ y ∈ L 2 }
    L * = {ε} ∪ L ∪ L 2 ∪…

    Вопросы
    • Какую классификацию грамматики ввел Хомский?
    • Какой класс грамматик соответствует машинам Тьюринга?

    Если вы не знаете ответа на эти вопросы, прочтите еще раз содержание выше.

    Каковы истоки английского языка?

    Каковы истоки английского языка?

    История английского языка условно, хотя, возможно, слишком аккуратно, разделена на три периода, обычно называемых староанглийским (или англосаксонским), среднеанглийским и современным английским. Самый ранний период начинается с миграции определенных германских племен с континента в Британию в пятом веке, году нашей эры, году, хотя никаких записей об их языке не сохранилось до седьмого века, и он продолжается до конца одиннадцатого века или чуть позже. потом.К тому времени латынь, древнескандинавский язык (язык викингов-захватчиков) и особенно англо-нормандский французский доминирующего класса после норманнского завоевания в 1066 году начали оказывать существенное влияние на лексику, и хорошо развитая флективная форма. система, которая типизирует грамматику древнеанглийского языка, начала разрушаться.

    Следующий краткий образец древнеанглийской прозы иллюстрирует несколько важных способов, которыми изменения настолько изменили английский язык, что мы должны внимательно поискать точки сходства между языком десятого века и нашим собственным.Оно взято из «Проповеди о св. Григории Великом» Элфрика и касается знаменитой истории о том, как этот папа пришел послать миссионеров для обращения англосаксов в христианство после того, как увидел англосаксонских мальчиков, выставленных на продажу в качестве рабов в Риме:

    Eft he axode, hu re ðeode nama wære þe hi of comon. Он был geandwyrd, это привет Angle genemnode wæron. Þa cwæð he, "Rihtlice hi sind Angle gehatene, для an ðe hi engla wlite habbað, и swilcum gedafenað t hi on heofonum engla geferan beon.«

    Некоторые из этих слов будут признаны идентичными по написанию с их современными эквивалентами - he, of, him, for и, on , - и можно угадать сходство некоторых других со знакомыми словами - nama to Имя , общее с по было, было с по , было с по было - но только те, кто специально изучил древнеанглийский язык, смогут прочитать отрывок с пониманием. Смысл в следующем:

    Опять он [св.Григорий] спросил, как могут быть имена людей, от которых они произошли. Ему ответили, что их назвали англами. Затем он сказал: «Их справедливо называют ангелами, потому что они обладают красотой ангелов, и уместно, чтобы такие, как они, были товарищами ангелов на небесах».

    Некоторые слова оригинала сохранились в измененной форме, в том числе axode (спрашивается), hu (как), rihtlice (правильно), engla (ангелы), habbað (имеют), swilcum (такой), heofonum (небеса). , и beon (be). Другие, однако, исчезли из нашего лексикона, в основном бесследно, в том числе несколько, которые были довольно распространенными словами в древнеанглийском: eft "снова," ðeode "люди, нация," cwæð "сказал, говорил , " gehatene " назвал, назвал, " wlite " внешний вид, красота "и geferan " товарищи ". Распознаванию некоторых слов, естественно, мешает наличие двух специальных символов, называемых «шип», и ð, называемых «edh», которые в древнеанглийском языке использовались для обозначения звуков, которые теперь пишутся как th .

    Другие моменты, на которые стоит обратить внимание, включают тот факт, что в конце десятого века система местоимений еще не включала формы множественного числа третьего лица, начинающиеся с th-: hi появляется там, где мы использовали бы они. Некоторые аспекты порядка слов также поразят читателя как странно непохожие на наши. Подлежащее и глагол меняются местами после наречия - þa cwæð he «Then said he» - явление, известное в современном английском языке, но теперь ограниченное несколькими наречиями, такими как never и требующими наличия вспомогательного глагола, такого как do. или имеют. В придаточных предложениях главный глагол должен быть последним, и поэтому объект или предлог могут предшествовать ему не естественным образом: þe hi of comon «откуда они пришли», для ðan ðe hi engla wlite habbað «потому что они обладают красотой ангелов».

    Пожалуй, самое отличительное различие между древнеанглийским и современным английским, отраженное в предложениях Элфрика, - это сложная система флексий, от которой у нас теперь остались лишь остатки. Существительные, прилагательные и даже определенный артикль склоняются в зависимости от рода, падежа и числа: ðære ðeode «(of) the people» - женского, родительного и единственного числа, Angle «Angles» - мужского, винительного и винительного. множественное число и swilcum «такой» - мужской род, дательный и множественное число.Система флексий для глаголов также была более сложной, чем наша: например, habbað «имеет» оканчивается суффиксом -að , характерным для индикативных глаголов присутствия во множественном числе. Кроме того, было две формы повелительного наклонения, четыре сослагательных наклонения (две для настоящего времени и две для претерит, или прошедшего времени), а также несколько других, которых у нас больше нет. Даже там, где современный английский сохраняет определенную категорию интонации, форма часто менялась. Старые английские причастия настоящего оканчивались на -ende , а не на -ing, и причастия прошедшего времени имели префикс ge- (как geandwyrd «ответил» выше).

    Период среднеанглийского языка простирается примерно с двенадцатого по пятнадцатый век. Влияние французского языка (и латыни, часто через французский) на лексикон продолжалось в течение всего этого периода, потеря одних интонаций и сокращение других (часто до последней безударной гласной, записанной как -e ) ускорились, и многие изменения имело место в фонологической и грамматической системах языка. Типичный прозаический отрывок, особенно из более поздней части периода, не будет иметь для нас такого чужеродного взгляда, как проза Элфрика; но это тоже не будет ошибочно принято за современную письменность.Следующий краткий отрывок взят из работы конца четырнадцатого века под названием «Путешествие Мандевиля года». Это художественная литература под видом литературы о путешествиях, и, хотя она претендует на то, чтобы быть написанной пером английского рыцаря, первоначально она была написана на французском языке, а затем переведена на латынь и английский язык. В этом отрывке Мандевиль описывает землю Бактрию, по-видимому, не совсем привлекательное место, поскольку она населена «полным юэле [злым] народом и полным жестоким».

    In at lond ben trees þat beren wolle, как и ogh, из Scheep; из которого люди шьют одежду, и все шитье может быть сделано из волка.In at contree ben много ipotaynes, þat обитал в сомтиме в воде и в сомтиме на лоне: и ei ben получеловек и полураск, как я haue seyd прежде; и ei eten men, когда ei может взять подол. И þere ben ryueres и watres þat ben fulle byttere, ree sithes more an - это вода моря. В at contré ben много griffounes, более полно an только в других contree. Sum men seyn at ei han тело вперёд, как игле, и благо как loun: и treuly þei seyn soth at ei ben of at schapp. Но у грифона больше печали и он сильнее, Шанне восемь лет, таких как у этой половины; и еще более печальный и сильный - сто яиц, таких как мы han betweenes vs.Ибо грифон ere будет бежать в свое гнездо a gret hors, 3 если он найдет его на пойнте, или двух волов, запряженных вместе, как ei gon на плуг.

    Орфография часто специфична по современным стандартам и даже непоследовательна в этих нескольких предложениях (contré и contree, o [griffoun] и a [gret hors], anne и an, , например). Более того, в оригинальном тексте, помимо шипа, есть еще один старый иероглиф 3, называемый «йог», чтобы усложнить задачу.Он может представлять несколько звуков, но здесь может быть представлен как эквивалент y. Однако даже старые варианты написания (в том числе те, где u обозначает v или наоборот) узнаваемы, и есть только несколько слов, таких как ipotaynes, "hippopotamuses" и sithes "times", которые выпали. из языка вообще.

    Мы можем заметить несколько слов и фраз, значения которых больше не используются, например, byttere «соленый», o этой половине «на другом конце света» и at the poynt «to hand» и Влияние многовекового господства французского языка на словарный запас проявляется во многих знакомых словах, которые не могли бы произойти в письме Элфрика, даже если бы его субъект позволял это, такие слова, как contree, ryueres, plentee, egle, и lyoun. .

    В целом порядок слов сейчас очень близок к современному, хотя мы замечаем, что такие конструкции, как , имеют тело больше, и , на три сиденья больше, - это вода моря. Мы также замечаем, что глаголы настоящего времени по-прежнему имеют склонение множественного числа, как в beren, dwellen, han, и ben , и что, хотя именительный падеж þei заменил Aelfric hi в третьем лице множественного числа, форма для объектов стоит еще руб .

    Тем не менее, количество наклонений для существительных, прилагательных и глаголов значительно сократилось, и во многих отношениях Мандевиль ближе к модерну, чем к древнеанглийскому.

    Период современного английского языка простирается с шестнадцатого века до наших дней. В начале этого периода завершилась революция в фонологии английского языка, начавшаяся в позднем среднеанглийском и фактически перераспределившая появление гласных фонем на нечто, приближающееся к их нынешнему образцу.(Английский язык Мандевиля показался нам даже менее знакомым, чем кажется.)

    Другие важные ранние разработки включают стабилизирующее влияние на орфографию печатного станка и начало прямого влияния латинского и, в меньшей степени, греческого языка на лексику. Позже, когда английский язык вошел в контакт с другими культурами по всему миру и отличительные диалекты английского языка развились во многих областях, колонизированных Британией, многие другие языки внесли небольшой, но интересный вклад в наш словарный запас.

    Исторический аспект английского языка действительно включает в себя больше, чем три стадии развития, которые мы только что рассматриваем. У английского языка тоже есть то, что можно назвать предысторией. Как мы видели, наш язык не просто возник; он был привезен с континента германскими племенами, не имевшими письменности и, следовательно, не оставившими никаких записей. Филологи знают, что они, должно быть, говорили на диалекте языка, который можно назвать западногерманским, и что другие диалекты этого неизвестного языка должны были включать предков таких языков, как немецкий, голландский, нижненемецкий и фризский.Они знают это из-за определенного систематического сходства, которое эти языки разделяют друг с другом, но не имеют общего, скажем, с датским. Однако им пришлось каким-то образом реконструировать, каким был этот язык в его лексиконе, фонологии, грамматике и семантике, насколько это было возможно, с помощью сложных методов сравнения, разработанных в основном в течение последнего столетия.

    Точно так же, поскольку древние и современные языки, такие как древнескандинавский и готический, исландский и норвежский, имеют общие черты с древнеанглийским и древневерхненемецким или голландским и английским, которых они не разделяют с французским или русским, очевидно, что существовала более ранняя незарегистрированный язык, который можно назвать просто германским и который необходимо реконструировать таким же образом.Еще раньше германский был просто диалектом (предки греческого, латыни и санскрита были тремя другими такими диалектами) языка, условно обозначенного как индоевропейский, и, таким образом, английский - всего лишь один относительно молодой член древней семьи языков, чьи потомки покрывают значительную часть земного шара.

    Структура языка

    Структура языка

    Структура человеческого языка

    Раздаточный материал для LING 057
    «Язык и народная культура».

    Когда мы думаем о компонентах человеческого языка, мы думаем о нем как о состоящий из следующего:

    1. Звуковая система (или фонологический компонент).
    2. Набор словарных единиц («лексика»).
    3. Грамматическая система («морфология»), придающая смысл элементы вместе в "слова".
    4. Синтаксис или набор правил для определения порядка элементов более крупные высказывания, такие как «предложения».
    5. Семантический компонент, в котором интерпретируются значения.

    Мы думаем об этих компонентах как о конечных и Остальные способы не конечны. И строительные блоки из одного компонента образуют единицы тех, кто выше него.

    1. Звуковая система способна на бесконечных минутных разниц. в звуке, но ни один язык не использует все или даже большую часть возможных различия. Звуковые системы делят объекты на конечные единицы (называемые "фонемы" или классы звуков) и, следовательно, количество звуковых единиц конечный т.е. английский имеет конечное количество гласных и согласные; количество гласных около 11 или 12, в зависимости от диалекта.
    2. Набор словарных единиц («лексика»).Набор значимых единицы конечны, или вроде как: часто встречаются «старые» (архаичные, устаревшие) слова, плавающие в языке, особенно в печати. Некоторые могут быть используется более старыми ораторами; некоторые могут быть признаны за их значение в контекст, но не был бы «известен» изолированно. Так старые смыслы уходят выходят, и постоянно придумываются новые слова.

      Набор значимых единиц в лексиконе, следовательно, более или менее конечный,

    , но не совсем то же самое для каждый оратор.Некоторые значимые единицы имеют только грамматических значение, например суффиксы в таких словах, как -ing, -s, -ed, -th (как в wid th и тд) и тд. Итак, мы различаем

    • лексический смысл и
    • грамматических значащих единиц.

    Грамматические морфемы более конечны, чем первые. Один пример довольно новый грамматический маркер - это суффикс «ребята», как в «вы, ребята», который обозначает множественность для множества людей.В других диалектах для этого есть "y'all". Дело в том, что он становится грамматическим маркером, это видно по тому, как некоторые люди его делают притяжательный, то есть «югайзиз», или в южных диалектах «йаллз»:

    • 'Ребята, вам нужно дать мне чеки, чтобы вы могли возмещения.
    • Вы должны дать мне чеки, чтобы вы могли получить возмещения.
  • Грамматическая система («морфология»), объединяющая значимые элементы в «слова».Грамматика конечна в любой момент.
  • Синтаксис или набор правил для определения порядка элементов более крупные высказывания, такие как «предложения». Но вывод синтаксиса, то есть предложения, которые люди знают и узнают, - это бесконечно.
  • Семантический компонент, в котором интерпретируются значения. Количество возможных значений, вероятно, тоже бесконечно.

    Объедините их в некую иерархическую структуру, используя звук система в качестве первых строительных блоков и работает вверх от там дает нам следующую структуру:

    Уровень структуры: Возможности:
    Семантика: Бесконечный.
    Синтаксис: предложения БЕСКОНЕЧНЫЙ
    Грамматика: довольно жесткий и фиксированный.
    Инновации на этом уровне идут медленно
    конечный
    Словарь, значащие единицы:
    несколько неограниченный, но по сути
    конечный
    Акустическая система, единицы звука конечный
    Фонетический уровень Бесконечный

    Мы видим такую ​​структуру, построенную с нуля, как одержимые.

  • Оставить комментарий

    Добавить комментарий

    Ваш адрес email не будет опубликован. Обязательные поля помечены *

    © 2019 Штирлиц Сеть печатных салонов в Перми

    Цифровая печать, цветное и черно-белое копирование документов, сканирование документов, ризография в Перми.