Является ли a* b * регулярным?

Я знаю,что a n b n для n > 0 не является регулярным по лемме накачки, но я бы предположил, что a*b* является регулярным, так как оба a, b не должны быть одинаковой длины. Есть ли доказательства того, что это регулярно или нет?

3 6
regular-language

3 ответа:

Ответ на ваш вопрос:

Представьте себе, что a * b * является регулярным, есть ли доказательство его регулярности или нет?

Не нужно представлять, выражение a*b* называется r egular e xpression (re), а регулярные выражения возможны только для регулярных языков. Если язык не является регулярным, то регулярное выражение также невозможно для этого, и если язык является регулярным языком, то мы всегда можем представить его с помощью какое-то регулярное выражение.

Да, a*b* представляет собой обычный язык.

Описание языка : любое число a далее следуют любые числа b (под любым числом я подразумеваю ноль (включая нуль ^) или более раз). Вот некоторые примеры строк: 

{^, a, b, aab, abbb, aabbb, ...}

DFA для RE a*b* будет выглядеть следующим образом: 

      a-            b-
      ||            ||
      ▼|            ▼|
---►((Q0))---b---►((Q1))

In figure: `(())` means final state, so both `{Q0, Q1}` are final states.

Вам нужно понять следующее основное понятие:

Что такое в основе своей обычный язык? И почему бесконечный язык 'a*b*' является регулярным, тогда как языки типа '{ a n b n | n > 0 } ' не являются регулярными!!

Язык (множество) называется регулярным языком, если он требует только ограниченного (конечного) количества информации для хранения в любой момент времени при обработке строк языка. Итак, что такое "ограниченная" информация?
Например: рассмотрим переключатель вентилятора "вкл." / " выкл.". При просмотре переключателя вентилятора мы можем сказать, находится ли вентилятор в состоянии on или off (это ограниченная или ограниченная информация). Но мы не можем сказать, что "сколько раз" вентилятор был включен и выключен в прошлом! (чтобы запомнить, требуется механизм для хранения "неограниченного" количества информации для подсчета - "сколько раз", например, какой-то счетчик использует в наших автомобилях/велосипедах).

Язык {anbn | n > 0 } не являетсярегулярным языком, поскольку здесь n неограничен(что может быть бесконечно большим). Проверка строк в языке a nb n , нам нужно запомнить, что сколькоa символы были получены, и это требует бесконечного хранения памяти для подсчета, потому что число a символы в строке могут быть бесконечно большими!

Это означает, что автомат способен обрабатывать строки языка a n b n только в том случае, если он обладает бесконечной памятью, например PDA.

Тогда как, a*b*, конечно, регулярна по своей природе, потому что существует ограниченное ограничение ‐ что b может быть, придут после некоторых a ( и a не может прийти после b). И именно поэтому каждая строка этого языка может быть легко обработана (или распознана) автоматом, в котором у нас есть конечная память - иконечные автоматы - это класс автоматов, где память конечна. Да, в конечных автоматах мы имеем конечное количество памяти в термине состояний.

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

Конечное состояние ⇒ конечная память ⇒ только язык может быть процессом, для которого конечная память должна храниться в любой момент времени при обработке строки ⇒ этот язык является называется регулярным языком

Отсутствие внешней памяти является ограничением конечного автомата ⇒ или мы можем сказать ограничением конечных автоматов определенного класса языка, называемого регулярным языком.

Вам следует прочитать другой ответ "конечность регулярного языка", чтобы узнать область применения регулярного языка.

Боковое Примечание::

  • язык { a n b n | n > 0 } является подмножеством a*b*
  • также Язык { a n b n | 10>100 n > 0} является регулярным, большим множеством, но регулярным, потому что n ограничено, следовательно, конечные автоматы и регулярное выражение возможны для этого языка.

Вы также должны прочитать:: Как доказать правильность языка?

15

Доказательство: ((a*)(b*)) является хорошо сформированным регулярным выражением, следовательно, соответствующим регулярному языку. a*b* - синтаксическое сокращение одного и того же выражения.

Еще одно доказательство: регулярные языки закрыты для конкатенации. а* - это обычный язык. b * является регулярным языком, поэтому их конкатенация, a*b*, также является регулярным выражением.

Для него можно построить автомат: 

0 ->(a) 1
0 ->(b) 2
1 ->(a) 1
1 ->(b) 2
2 ->(b) 2
2 ->(a) 3
3 ->(a,b) 3
Где только 3 не является принимающим состоянием, и докажите, что язык является a*b*.
2

Чтобы доказать регулярность языка, достаточно показать либо:

1) существует некоторый DFA, который распознает его. В этом случае DFA является тривиальным.

2) язык может быть выражен в виде регулярного выражения, как указано в другом ответе. a*b* - регулярное выражение для распознавания этого языка.
0