# Tag Info

Accepted

### FSA for 'closure' of a language; how to represent?

As far as I can tell, you are asking about constructing an $\epsilon$-NFA $B$ from a DFA $A$; such that $L(B) = L(A)^*$. If yes, please edit the question, and write it more clearly. Well, your ...
• 3,176
1 vote

### Reachable States in a Product of Transition Systems

You can use the same method for finding the reachable states in any transition system. Construct the transition graph for the system $A1 \times A2 \times A3$ (constructed using the product ...
• 162k

### Derivation for BNF

You don't need to write [EMPTY] but you do need to remember that it takes one step to replace LetterTail with the empty sequence....
• 470
Accepted

### Splitting strings in pumping lemma for regular language

When using the pumping lemma to prove that a language is not regular, you cannot just find ONE decomposition $xyz$ that does not satisfy the three properties: you must prove that ANY decomposition ...
• 15.9k
1 vote

### Implementing regular expression matching using Brzozowski derivatives

Other answers here help answer the other questions as to advantages and disadvantages of the approach you suggested; I'm just sharing another place where it's used in case you're interested. Lotz et ...

### Is garbage state necessary in DFA that enforces a particular input combination?

Recall that in the case of a DFA, the transition function $\delta: Q\times \Sigma \rightarrow Q$ is a total function. This implies that on each state $q \in Q$, there should be an out-going transition ...
• 1,797
Accepted

### Is garbage state necessary in DFA that enforces a particular input combination?

In short: yes, a DFA for the language $1(0+1)^*$ needs at least 3 states. In order to prove this, you can use the Myhill-Nerode theorem, which states that the size of the minimal DFA for a language is ...
• 17.3k
Accepted

### Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?

Yes, this is totally possible. The product-construction you use has an edge $((p,p'),a,(q,q'))$ if the original automata have edges $(p,a,q)$ and $(p',a,q')$. In the picture below I have an example of ...
• 30.7k
Rather than directly using the pumping lemma, you can use the closure property of context-free languages. I use $L_1 := \{1^{2n}0^n \mid n \geq 0\}$ and $L_2 := \{1^n0^{2n} \mid n \geq 0\}$ to show \$L ...