Беседа:Йерархия на Чомски

Искам да разширя статията за йерархията на Чомски и искам да питам две неща за българската терминология:

• как наричаме context-sensitive граматики/езици?
• как е closure (нем. Hülle) на български? Обвивка?

--Станислав 07:48, 10 мар 2005 (UTC)

Граматиките съм ги учил като контекстни и безконтекстни. За обвивка си прав. --Борислав 08:02, 10 мар 2005 (UTC)

Мерси.. Имам един друг въпрос: няма ли да е по-добре да използваме <math> навсякъде, където се срещат изрази, било то и за една единствена променлива в текста:

Дадено е множество $A$ (извън $\alpha \cup \beta$).

$A\subset B\cup \lbrace 0,1,\pi \rbrace$

vs.

Дадено е множество A (извън α ∪ β)

$A\subset B\cup \lbrace 0,1,\pi \rbrace$

Причините са: (а) италикса често лошо се съчетава с другия текст (b) смесваме серифи, което прави променливи и пр. нееднакви ($B\neq \mathbb {B} \neq {\mathcal {B}}$) (c) символите не винаги съотвестват напълно, което може да обърка читателя (→ vs. $\rightarrow$). --Станислав 10:35, 10 мар 2005 (UTC)

Аз май съм за използването на <math>, въпреки че и с него понякога се генерира HTML. --Борислав 14:26, 10 мар 2005 (UTC)

---

Друго за латех: има ли начин да се центрира звездата в $\Rightarrow ^{*}$ (звездата обозначава рефлексивната транзитивна обвивка, което не искам да се бърка със значението "всички низове", което съще се ползва в текста). За предпочитане нещо без таблици/матрици (\stackrel не работи). --Станислав 10:42, 10 мар 2005 (UTC)

Ами, звездата се използва и в двата случая. Има ли наистина нужда да я променяме (с \Rightarrow* се центрира, но се отдалечава от релацията)? Все пак от контекста се разбира за какво е: ако е поставена на релация, обозначава рефлексивната транзитивна обвивка, а ако е на множество — всички низове, построими с елементите му. Добре, че няма и регулярни изрази . --Борислав 14:26, 10 мар 2005 (UTC)

Имах предвид да се центрира хоризонтално над стрелката:

   \|/
    X
   /|\
         \
----------\
----------/
         /

. Не че е голям проблемът, но нужда мисля има, защото и релацията е множество, а в текста другата релация ($\rightarrow$) се третира/дефинира като такова. --Станислав 14:53, 10 мар 2005 (UTC)

Още термини

За pushdown automaton на немски за ползвали превод на stack. Възможно е в българския да има термин стеков автомат (stack обикновено не го превеждат). За езиците: rekursiv abzählbar също бих го превел рекурсивно изброим, но в учебника ми по дискретна математика се срещаше терминът рекурсивно номерируем. Мисля си, че би било хубаво да направим една страничка с такива термини, независимо дали знаем българските съответствия. Така някой с повече познания би могъл да ги попълни. --Борислав 14:42, 10 мар 2005 (UTC)

Мисля си, че писателя е преписвал от английски (enumerable) и нещо не е съобразил превода? --Станислав 15:07, 10 мар 2005 (UTC)

Автоматите детерминирани ли са или детерминистични? --Борислав 15:58, 12 мар 2005 (UTC)

Термина е детерминистична машина на Тюринг (поне на английски и немски). детерминистичен се различава от детерминиран по следния начин:

• детерминистичен : стъпките, които се извършват са детерминирани
• детерминиран : крайния резултат е детерминиран (по-слабо изказване)

Проверих току-що в една книга, че става въпрос именно за детерминистичен. --Станислав 16:21, 12 мар 2005 (UTC)

Срещал съм само (не)детерминирани крайни автомати, та затова попитах. Какво означава „крайният резултат е детерминиран“? --Борислав 12:54, 13 мар 2005 (UTC)

deterministic/deterministisch/(„детерминистичен“ (мисля)) е термина, който се използва за алгоритми, машини и пр., за да се укаже, че стъпките са еднозначни:

• в случая крайни автомати: за дадено състояние и входящ символ има най-много едно следващо състояние и няма ε-преходи, освен тривиални (= несменящи състоянието)
  • (за всеки недетрминистичен к.а. може да се построи детерминистичен к.а., разпознаващ същия език)
• в случая TM: за дадено състояние и символ на лентата има най-много една следваща конфигурация (т.е. нямаме избор за ново състояние, нов символ и вид движение)
  • (не се знае, дали за всяка недетерминистична линейно ограничена TM може да се укаже детерминистична такава, разпознаваща същия език)

determinate/determiniert/детерминиран е термин, който по-принцип го знам за алгоритми. Той указва, че при даден вход, макар и стъпките да може да са нееднозначни (=недетрминистичен алгоритъм), крайният резултат е еднозначен. В Гугъл гледам [1], че в научни текстове се използва и за машини: за тези, които имат само "локален" недетерминизъм, т.е. графовете им имат нещо като свойството на Чърч-Росер (нем. Konfluenz), т.е. когато се разделят пътища, всички в крайна сметка водят пак до едно място.

И в двата случая (алгоритми и машини), ако имаме детерминистичност, автоматично имаме и детерминираност. Така че в случая за машините, "детерминиран" се използва по-скоро за разграничаване на недетрминистични машини с такова свойство, и съответно смятам, че "недетерминиран" би трябвало да се използва в контекста на такова свойство (а не в нашия), въпреки че, що се отнася до разпознаването на езици, ми изглежда, че няма разлика в класовете. (За други употреби на машини, естествено, има разлики.) --Станислав 23:44, 14 мар 2005 (UTC)

Корекция на задрасканото: Всъщност, и двата термина, ако ще дефинират клас машини, ще се ползват не в комплементарен смисъл, а във включващ: недетрминистичните машини ще включват детерминистичните и съответно недетрминираните ще включват детерминираните, като специален случай. В този смисъл: недетерминистични=недетерминирани=нерозови=некаквито-и-да-било, защото "не" семантично означава "всички, без ограничение на свойството". Причината да се спрем на думата „детерминистичен“ е, че това свойство образува правилния контраст: изчислителната мощ в този случай зависи от детерминистичността (или по-скоро се смята, че зависи; не е доказано), а не от детерминираността. --Станислав 05:08, 15 мар 2005 (UTC)

Пропуснах да отбележа, че говорех за български. На английски и немски и аз така го знам, но на български само като детерминирани (с това не казвам, че преводът е бил правилен ). А магазинните автомати са ми познат термин, как не се сетих за тях... --Борислав 08:31, 15 мар 2005 (UTC)

Промени

ехо. гледам бая промени сте сложили. и благодаря. професионалния подход е добър, аз обаче настоямвам или: да въведете понятията като статии в уики за терминални/нетерминални символи, или да им сложите някакво обяснение в текста, щото не е много ясно за незапознатите, лингвистите(като мен) се З?/+?/+_:/_.

Благодаря за съдействието. Александра ПС. аз продължавам да правя статии в лингивстиката, но ако някоя от тях е повече или по-малко свързана с математиката ще ви благодаря да се включвате. БТВ няма нищо в раздел за формални езици, тва е тъпо, щото е съществено. Въобще ръздел математика е почти празен според мене.

Съгласен съм, има още работа по статията; ще се опитам да подобря разбираемостта в следващите дни. Що се отнася до математика/лингвистика/формални езици, наистина имаме още страшно много дупки. Надявам се да се попълват постепенно... --Станислав 17:27, 10 мар 2005 (UTC)

Връзките към лингвистика и САЩ

бяха махнати като косвени. За лингвистика това със сигурност не се отнася (йерархията има голямо значение за лингвистиката (недостатък на статията е, че това не се споменава (още)) и често се учи във въвеждащите курсове). Връзката към САЩ наистина е косвена, но аз лично съм привърженик на някои косвени препратки (стига да не са до абсурдна степен). Самият "чомскиизъм" в лингвистиката е силно Американско-базиран...

Да, прав си, лингвистиката е в пряка връзка, просто препратката не беше за изречението. --Борислав 15:54, 12 мар 2005 (UTC)