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

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

Теорема о детерминизации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Детерминированные автоматы с магазинной памятью - это автоматы с магазинной памятью, которые 

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

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

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

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

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

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

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

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

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

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

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

Чтобы получить полезный и естественный с точки зрения практики класс языков, нужно

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

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

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

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

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

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

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

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

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

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

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

Маркером конца слова по своей сути является

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

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

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

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

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

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

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

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

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

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

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

Автомат с магазинной памятью называется детерминированным, если

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эквивалентность автоматов с магазинной памятью доказывается с помощью

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

&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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рабочая гипотеза 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 неразрешима.

Доказательство: То, что точка доступа узнаваема, отображается так же, как и для язык 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).

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

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 ³ log2 ⁿ )
Время выполнения неэффективных алгоритмов
O (2 ⁿ ), 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 слишком общие, чтобы описывать синтаксис языков программирования и естественных языков.

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

Пример:

AB → CDB

AB → CdEB

ABcd → abCDBcd

B → b