Skip to main content

New answers tagged

2 votes
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 ...
Bader Abu Radi's user avatar
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 ...
D.W.'s user avatar
  • 162k
0 votes

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....
Li-yao Xia's user avatar
4 votes
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 ...
Nathaniel's user avatar
  • 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 ...
TailRecursion's user avatar
0 votes

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 ...
codeR's user avatar
  • 1,797
4 votes
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 ...
Shaull's user avatar
  • 17.3k
3 votes
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 ...
Hendrik Jan's user avatar
  • 30.7k
3 votes
Accepted

Are Context-Free languages closed under XOR?

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 ...
pcpthm's user avatar
  • 2,817

Top 50 recent answers are included