# Tagged Questions

95 views

### Can you draw the e-NFA from the following definition?

I am trying to understand the solution, because I think I got it completely wrong. I wrote we could take the initial DFA and replace the normal transitions with epsilon transition except for all ...
67 views

### Prove or disprove that the language $L_1 = \{a^nb^m \mid n < m \}$ is regular

I have possible strategy for a proof that it is not regular. I am wondering if it is valid. Step 1: Prove that the language $L_2 = \{a^nb^n\}$ is not regular (for example with the Pumping Lemma). ...
353 views

### Proof of Equivalence of NFA and DFA, quick question about the setup

I am looking at the proof of equivalence of non determinstic finite automata(NFA) and deterministc finite automata(DFA). I am have a small quesion about the construction: Let ...
96 views

### Show that, given regular expression $R$, we can decide whether $L(R)$ is prefix-free

Suppose language $L$ is called prefix-free if no member is a proper prefix of another. For instance, cat is a proper prefix of category and so $L = \{cat,category,ego,go,rye\}$ is not prefix free. ...
47 views

### Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
26 views

### Give a regular expression for $A = \{1^{k}y|k \geq 1, y \in \{0,1\}^{*}$ and $y$ contains at least $k$ $1$'s $\}$

The regular expression that is given is $1(0 \cup 1)^{*}10^{*}$. I'm having trouble realizing why this regular expression describes the language given. For example, the string (for $k$ = 4) $1111$ ...
107 views

### Proving $L=\{0^n \mid \text{n is a perfect square}\}$ is not a Regular Language without the Pumping Lemma

Is this a valid way of going about proving the proposition? Let $L = \{0^n \mid \text{n is a perfect square}\}$. The regular languages are closed under concatenation. So if $x \in L, y \in L$, then ...
56 views

### Formal proving of languages accepted by a finite automata.

Suppose $L_1 \cup L_2,L_1 \subseteq E^*$ are languages accepted by finite automata and $L_1\cap L_2 =\emptyset$. We need to prove that $L_2$ is also accepted by a finite automaton. So I've started ...
175 views

### DFA Transition Function Inductive Proof

Show for any state $q$, string $x$, and input symbol $a$, $\hat\delta(q, ax) = \hat\delta(\delta(q, a), x)$, where $\hat\delta$ is the transitive closure of $\delta$, which is the transition function ...
233 views

### Show that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.