11
You are indeed allowed to have unreachable states in DFAs (or NFAs, or various other automata models).
You may wonder what is the point of having them, given that they are unreachable and have no effect on the language.
Well, automata are typically not designed by hand. Rather, they are usually obtained algorithmically by translation from other types of ...
7
Check the definition. It usually goes like $M = (Q, \Sigma, \delta, q_0, F)$, with $Q$ a finite set of states, $\Sigma$ the (input) alphabet, $\delta \colon Q \times \Sigma \to Q$ the transition function, $q_0 \in Q$ the initial state, $F \subseteq Q$ the set of final (accepting) states. Note that the only condition on $\delta$ is it being a function. To ...
4
This problem can be solved in polynomial time by a product construction. Construct the graph $G^\prime$ as follows:
The vertices of $G^\prime$ are $(V \times M) \cup \{\#\}$, i.e. all pairs of a vertex of $G$ and a state of $M$, together with an extra vertex identified by the arbitrary symbol $\#$.
For each edge in $e \in E$ from $v_1$ to $v_2$, add an edge ...
3
The quoted answer does not claim that every right regular grammar is LL(1). That statement would not be true.
What the answer claims is that the grammars produced by the indicated algorithm are LL(1). That statement is correct.
So, no-one is saying "every right-linear grammar" satisfies condition 1 (of the LL(1) definition) (your Q1). They don't all do so.
...
2
You should look into Theory of Automata, Languages and Computation:
These are the theoretical foundations of scanning, parsing and processing text (and furthermore constructing formal languages and grammars).
Components of the theory, are, for example:
Pushdown automaton
Context free grammars
Parsing techniques such as recursive decent, LL or SLR parsing.
...
2
Let $M$ be a DFA for the language $L$ and let $M_1$ and $M_2$ be $M$ with two different collections of some number $m$ of unreachable states added. $M_1$ and $M_2$ both have the same number of states and both accept $L$, but they need not be isomorphic.
For a less trivial example, consider the following two DFAs:
Start state: 1
Accepting states: 2, 4
1 -a-&...
1
For your specific question, you are asking to generate a string in $\bar{L} \cap P$. Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free. It is known that the intersection of a regular and context-free language is context-free. So, you're asking: given a context-free language, how do we generate a word in that language? ...
1
Your second method to arrive at $\phi$ is bogus - consider the case where $B$ is the empty language. Where you are confused here is you are looking at the difference between the sets of all regular languages and all context free languages, instead of the difference between the two concrete languages.
The correct answer is d. None (you can't say anything)
...
1
$L_1\circ L_2$ can certainly still be non-regular. For example, when $L_1$ contains exactly one word.
However, $L_1\circ L_2$ can be regular, too. Here is an example. Let $L_1=\{\epsilon,0\}$. Let $L_2$ be the complement of $\{ 0^n1^n \mid n \gt 0 \}$.
As the complement of a non-regular language, $L_2$ is not regular while $L_1\circ L_2$, the set of all ...
Only top voted, non community-wiki answers of a minimum length are eligible
