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

### от Уикипедия, свободната енциклопедия

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

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

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

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

    Мерси.. Имам един друг въпрос: няма ли да е по-добре да използваме `<math>` навсякъде, където се срещат изрази, било то и за една единствена променлива в текста:
      Дадено е множество A (извън ).
            vs.
      Дадено е множество A (извън α ∪ β)

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

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

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

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

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

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

    . Не че е голям проблемът, но нужда мисля има, защото и релацията е множество, а в текста другата релация () се третира/дефинира като такова. --Станислав 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)

Взето от „http://bg.wikipedia.org../../../%D0%B9/%D0%B5/%D1%80/%D0%91%D0%B5%D1%81%D0%B5%D0%B4%D0%B0%7E%D0%99%D0%B5%D1%80%D0%B0%D1%80%D1%85%D0%B8%D1%8F_%D0%BD%D0%B0_%D0%A7%D0%BE%D0%BC%D1%81%D0%BA%D0%B8_fcdf.html“.

##### Views

- Статия
- Беседа
- Текуща версия

##### Търсене