То, что обычный язык пересекается с 1 * 0 *, дает 1n0n

Question

Я читаю книгу по теории автоматов, и в книге приведен пример того, что язык с равным числом 0 и 1 пересекается с 1 * 0 *, в результате получится 1n0n, где n> 0

Итак, мой вопрос: как мне найти некоторые обычные языки, которые при пересечении с 1 * 0 * также приводят к 1n0n. Есть ли способ думать об этом?

обновление: Спасибо за ответы! Я думаю, что я пытаюсь найти некоторые обычные языки, поэтому такие как 1n0n не будут работать;) Является ли это возможным? Есть идеи?

Answer 1

Просто представьте себе вопрос как: «Какие языки, если они пересекаются с 1n0m, дают язык 1n0n?» В основном, все, что добавляет ограничение, что n = m.

Один из примеров - anbn, где a! = B. Еще один - L = { 1n0n1m0m | n!=m, n >= 0, m >= 0 }.

Кроме того, как указал OrangeDog, 1n0n не является регулярным, и поскольку обычные языки закрыты на пересечении, из этого следует, что любой язык, пересечение которого с 1*0* дает 1n0n, не является регулярным.

Answer 2

N.B. Язык с одинаковым и неограниченным числом 0 и 1 не является обычным языком.

Что касается вашего вопроса, я не думаю, что есть какие-то дополнительные ограничения, которые вы можете добавить к , некоторые из которых следуют за некоторыми нулями , чтобы получить n, за которыми следуют n нулей кроме двух, которые вы дали.

Существует бесконечное число тривиально построенных языков, которые удовлетворяют условиям: A1nB0nC, где A, B и C - любые выражения, которые могут соответствовать нулевой ширине.