Учитывая следующую формулировку:Является ли следующее langauge регулярным? контекст бесплатно?
L = { bi | i > 0 } U {aibi | i > 0 }
бесплатно Является ли этот язык контекст? регулярные?
Я пытался думать об этом, но никаких результатов до сих пор ..
L =
{ bi | i > 0 } U {aibi | i > 0 }не является контекстно-свободные или регулярный язык?
Язык L является «Context Free Language», В языке L {aibi | i > 0 } это подмножество строк, делает L контекстно свободный язык, который означает, что если строка начинается с a, то строка должна иметь равное количество b (в префиксе), и для подсчета количества a s нам понадобится память PDS (это не могут быть процессы с использованием FA из-за ограниченной памяти, доступной в FA).
Грамматика для L будет:
S --> A | B
B --> b | Bb
A --> ab | aAb
Подсказка для грамматики: либо строка может начинаться с b и может содержать любое количество b (если строка начинается с b то никакое a разрешено). Если строка начинается с a, тогда строка patter должна быть {aibi | i > 0 }.
Предлагаю вам прочитать: «Что такое обычный язык?» What is basically a regular language? And Why a*b* is regular? But language { anbn | n > 0 } is not a regular language
Это можно доказать либо с помощью леммы накачки, либо путем реализации того факта, что язык содержит бесконечное число попарно различимых строк. FSA с ограниченной памятью не может принять то же самое.
Язык может быть доказан как CFL, написав CFG (как указано в @Grijesh), который генерирует то же самое или путем создания Push Down Automata.
В дополнение к тому, чтобы быть свободным от контекста языком указанный язык: L = {b i | i> 0} U {a i b i | i> 0}
также является детерминированным контекстом свободного языка. Детерминированные CFL - это подмножество языков свободного контекста, которые закрыты под комплимент и пересечение, в отличие от класса CFL. Детерминированные CFL также закрыты при пересечении с регулярными языками, что помогает нам доказать, что данный язык является DFCL.
L∪R = (L с ∩ R с) с