All geek questions in one place

Computational Theory - shows that the language is regular

I am looking through some notes for my course, Computational Theory, and I am a little fixated on showing the following statement, and I was hoping someone could help me explain :)

Let A be the right language. Language B = {ab | a exists in and b does not exist in *} Why is B an ordinary language?

Some points are obvious to me. If b is just a constant string, this is trivial. Since we know that a is in and b is a string, regular languages ​​are closed under the union, so the language union that takes these two lines is obviously regular. However, I am not sure that b is constant. Maybe this is so, and if so, then this is not a problem. It’s hard for me to understand this. Thanks!

+4
source share
3 answers

You can prove by construction: Give a regular expression that B recognizes. The class of regular languages ​​is closed with respect to union, concatenation, star and complement.

+6
source

a and b in the question are not constant lines, but any lines, and B is the language of the lines with the beginning of line c and the end of the line not belonging to A. Now, since any regular language can be recognized by a regular expression, if Ra is a regular expression for recognition language A, then Ra , associated with the regular expression " not Ra ", is a regular expression for recognizing the language B. Since B can be recognized by the regular expression, it is a common language.

Edit: I first skipped the star after A at the end of definition B in the question. To account for this, make part of the regular expression that recognizes b also includes a star.

+4
source

B is a regular language because it ends when input "b" appears. we can write a regular expression for a given language B as a * b

0
source

Source: https://habr.com/ru/post/1306593/

More articles:


All Articles