# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

39 views

### Prove the infinite union is not regular

Prove $\bigcup _{i=1}^\infty A_i$ is not regular. We know $A_i$ is regular, but how can prove the infinite union is not regular. I think a counter example would work, but I can't think of any. ...
75 views

### Show a language is regular with Myhill-Nerode Theorem

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular? Take language $0^*1^*$ for example. I know this ...
27 views

### Prove that the Language $L= \{ 0^n1^m \;|\; n,m \ge 0 \}$ is regular

I've looked and didn't find an answer. I know that languages like $\{ 0^n1^n \;|\; n \ge 0 \}$ and $\{ 0^n1^m \;|\; m \gt n \ge 0 \}$ are irregular so I don't understand how this language can be a ...
27 views

### Which automata recognizes the language defined by the regular expression

I am trying to understand why the following NFA is the one which recognizes the language defined by the regular expression: $(00+10)0^*((1100+1110)0^*)^*$ As far as I can see the NFA will get stuck ...
81 views

### Pumping Lemma for $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$

Let $L=\left\{0^i 1^{j} \mid \gcd(i,j) = 1\right\}$ I want to prove that this is not a regular language, but I am having trouble finding a string I can pump resulting in the string not being in the ...
795 views

### Minimum Pumping Length

What is the minimum pumping length of (01)* The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be 0. ...
60 views

### Closure property of regular language

I am trying to prove the closure property of regular language with a function $f(w)$ over alphabet $\Sigma$ for any string $w \in \Sigma^*$. $f(w) =$ string obtained by taking symbols of $w$ at even ...
28 views

### Context free grammar for these langauges?

I've been working on trying to generate context free grammars for different problems and currently I'm working on these but after trying over and over, I can't come up with ones for these: 1) the ...
22 views

### Closure property of regular languages

I am trying to understand the closure property of regular languages. I am defining two functions func1(w) and func2(w) over alphabet Σ for any string w ∈ Σ∗. func1(w) gets the string of symbols of w ...
31 views

### What does it mean “the transition function of FA M is derivable in CFG G”?

I don't understand this question. Let $M$ be a finite automaton. If every production of G is accepted by M and the transition function of $m$ is derivable in G, then $L(G)$ = $L(M) ?$ What does ...
31 views

### Is the concatenation of two arbitrary alphabets is considered an alphabet?

Is the concatenation of two arbitrary alphabets is considered an alphabet ? Also Is the set of all Java reserved words is considered an alphabet ? I am inclined to say yes. We could take a string and ...