i saw this nice exercise in some old summary and i was wondering if i got it correctly. basically i have to decide whether a language is regular or not and give a short explanation. (languages over $\Sigma \{0,1,\$\}$)
1)$x_i,y_i,z_i \in \{0,1\}$ for every $1\leq n$, so that $x_1y_1z_1...x_ny_nz_n|x_n....x_1+y_n...y_1=z_n....z_1$
2){x$y$z | x + y = z} ($x,y,z \in \{0,1\}^+ $)
3)number of combinations of 01 in w = number of combinations 10 in w ($w \in \{0,1\}^*$)
my try:
1)not regular because n not seem to be bounded, and regular languages should have a finite boundary. however, maybe because of the addition i am missing something and it is actually bounded, but i think that it is not regular because the previous explanation.
2)since it is a finite set, we can use the pumping lemma to assert it is a bounded and thus a regular language.
3)not regular because number of combinations can be infinity, and because of the pumping lemma, a regular language should have a finite boundary.
for some reason when i try to use latex, it removes my {}, which are neccesary in logic and automata, and i don't know how to handle it to make it more readable.
tried to do my best and explain what i did and why and hope it's correct. if not, please correct me so i can learn from your answers and my mistakes and improve.
thank you very much!
A regular language is one that can be represented by a finite state automata, which is a very simple "machine" that doesn't have the ability to store any memory. That should give you a hint as to whether something is regular or not.
For instance, in the second language:
{xyz | x + y = z} (x,y,z∈ {0,1}+)
The value for "z" is dependent upon knowing the values of x and y, but these simple FSAs have no way of remembering that information. Keep in mind that the pumping lemma can be used to prove that this (and other languages) are NOT regular, but it cannot be used to prove that a language IS regular as you're asserting in your second point.