Как "δ:Q×Σ→Q" читается в определении DFA (детерминированного конечного автомата)?

Question

Как ты скажешь δ: Q × Σ → Q по-английски? Описывая что × а также → значит тоже поможет.

Answer 1

δ это как математическая функция, называемая функцией перехода. Что-то вроде.

z = f(x, y) 

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

[ОТВЕТ]

В выражении "δ:Q×Σ → Q",

× означает декартово произведение (то есть множество), а → отображение.
"δ:Q×Σ → Q" говорится δ является функцией перехода, которая определила отображение из Q×Σ в Q, Где, Домен δ является Q × Σ и диапазон Q,

Примечание: декартово произведение само по себе математическое, что все возможные пары заказов (сопоставления) между двумя наборами.

Вы также можете сказать:

δ является функцией перехода, которая определяет отображение между (или, скажем, ассоциированными) декартовым произведением множества состоянийQ и языковые символыΣ в набор государстваQ, Это сокращенно δ: Q×Σ → Q

Вот, Q конечный набор состояний и Σ это конечный набор языковых символов.

Кроме того, в любой автоматизированной вы можете представить функцию перехода в виде дерева.
1. Переходная таблица
2. График переходов или, скажем, диаграмма состояний.
3. Функция перехода: конечный набор правил отображения. например, {δ(q0, a) → q1, δ(q1, a) → q2}
_{Все для той же цели определяют отображение}

В ДФА. δ:Q×Σ → Q также может быть написано как δ(Q,Σ) → Q Это похоже на функцию. В δ Функция двух входных аргументов: состояние Q и символ языка Σ и возвращаемое значение Q,

Что означает δ(Q,Σ) → Q

Предположим, в вашем наборе функции перехода δ у тебя есть элемент δ(q0, a) → q1 это означает. Если настоящее состояние q0 затем потребляя a символ вы можете перейти к состоянию q1, И диаграмма состояния для δ(q0, a) → q1:

(q0)---a---►(q1)  

и таблица переходов:

+----+----+
|Q\Σ | a  |
+----+----+
| q0 | q1 |
+----+----+

и все определяет отображение (q0, a) to (q1),

Некоторые авторы пишут δ ⊆ Q×Σ → Q в формальном определении DFA это означает δ является частичной функцией (не определена в полном домене Q×Σ). Мы всегда можем определить δ на полном домене, который требуется когда-нибудь, например, чтобы найти дополнение DFA. Здесь ( Дополнение DFA) я написал два DFA для одного и того же языка, один - частичный DFA, другой - дополнительный DFA.

Answer 2

Извините, если условия не совсем верны (на английском языке). Я изучаю теорию автоматов около 3 или 4 лет назад на другом языке, поэтому термины могут быть не совсем точными.

δ подобна частичной функции с двумя аргументами, которая принимает в качестве входных данных состояние (состояние этого автомата; элемент Q) и "входное действие" (элемент Σ, который является алфавитом, принимаемым автоматом *), и создает новое состояние автомат должен иметь после предоставления ему входное действие.

В основном это можно прочитать как:

функция дельта-перехода, определенная на множестве состояний автоматов и сигма-алфавите

Символ × в формуле представляет декартово произведение наборов состояний и действий, а символ → означает, что возвращаемая функцией функция принадлежит следующему за ней множеству (в вашем случае Q).

* не следует путать с языком, принятым автоматом, который будет представлять собой все последовательности "входных действий", которые имеют допустимые переходы (т. е. определено δ(stateX, input)) и приводят автомат в конечное "приемлемое" состояние.

Answer 3

Дельта от сиг кросс сигма к кий

или же

Функция перехода, дельта, которая отображает упорядоченные пары состояний и входные символы, сигма пересечения сигма, состояниям, метка.

Answer 4

Это легко процитировать из Википедии:

δ - таблица перехода состояний: я бы прочитал "×" как таблицу, а "→" как записи в этой таблице.

Затем на естественном языке: укажите, какое состояние (элемент Q) будет результатом того, что машина находится в указанном состоянии и видит определенный символ (элемент из Σ).