Правило сплайсинга

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

Определение

Пусть A — алфавит, а L — язык, т. е. подмножество свободного моноида A. ^∗ . Правило сплайсинга — это четверка r = ( a , b , c , d ) элементов A ^∗ , а действие правила r на L заключается в создании языка

$r(L)=\{xady:xabq,pcdy\in L\}\ .$

Если R — набор правил, то ( L ) — это объединение языков, созданных правилами R. R Мы говорим, что R уважает L если R ( L ) является подмножеством L. , R - замыкание L — это объединение L и всех итераций R на L что оно соблюдается R. : очевидно , Язык сплайсинга — это R -замыкание конечного языка.

Набор правил R является рефлексивным , если ( a , b , c , d ) в R подразумевает, что ( a , b , a , b ) и ( , d , c , d ) находятся в R. c Язык сплайсинга является рефлексивным, если он определяется рефлексивным набором правил.

Примеры

• Пусть А = { а , б , с }. Правило ( caba , a , cab , a ), примененное к конечному множеству { cabb , cabab , cabaab }, порождает регулярный язык caba ^∗ б .

Характеристики

• Все языки сплайсинга являются регулярными.
• Не все обычные языки поддерживают сплайсинг. Пример: ( аа ) ^∗ над { a , b }.
• Если L — регулярный язык в алфавите A , а z — буква, не входящая в A , то язык { zw : w в L ) является языком сплайсинга.
• Существует алгоритм, позволяющий определить, является ли данный регулярный язык языком рефлексивной склейки.
• Набор правил сплайсинга, соответствующих регулярному языку, можно определить из синтаксического моноида языка.

Ссылки

• Андерсон, Джеймс А. (2006). Теория автоматов с современными приложениями . При участии Тома Хэда. Кембридж: Издательство Кембриджского университета . ISBN  0-521-61324-8 . Збл   1127.68049 .