New answers tagged regular-languages
0
The sticking point is in the first statement:
CFL is not closed under intersection. That means, if we have L1,L2 of CFL then
L1 intersection L2 is not a CFL
This is not what non-closure means. What it actually means is that the intersection of two languages from a given set may not be in the given set, so in this case "CFL is not closed ...
1
Every CFL language can be describes as a PDA. Every regular language can be described as a DFA.
The orthogonal product of a DFA and PDA can be defined as follows:
The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \...
0
Be careful, $L_1 \subseteq L_2$ with $L_2$ regular doesn't always mean that $L_1$ is regular. For one example, pick $L_1 = \{a^n b^n \colon n \ge 1\}$ (usually the first language proven non-regular), $L_2 = \mathcal{L}(a^* b^*)$ (defined by a regular expression, thus regular).
1
You need to use one intersection operation. It is a known closure property that if two languages $A, B$ are regular, then the intersection $A \cap B$ will also be regular. In this case, $A$ is the given regular language. The other one, $B = \textrm{Even}(\Sigma^*)$, is the language of all even-length strings. The language you want to prove is the language ...
1
Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?
0
Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows:
$\begin{align*}
h_1(x) &= \begin{cases}
x & x \in \Sigma \\
\sigma & x = A \text{ (a new symbol)}
\end{cases} \\
h_2(x) &= \begin{cases}
x & x \in \Sigma \\
\tau & x = A
\end{cases} \...
2
There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here ...
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? ...
8
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 ...
13
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 ...
0
Hint:
You are right on (a). The proof involves key results for Kleene star as follows.
$$
\Sigma^{*}=\bigcup_{n\geqslant1}\Sigma^{n}\quad\text{and}\quad L\Sigma^{*}=\bigcup_{n\geqslant1}L\Sigma^{n}\quad\text{and}\quad \Sigma^{*}L=\bigcup_{n\geqslant1}\Sigma^{n}L
$$
Where $\Sigma^{n}$ can be considered as the set of the concatenation of i strings in $\Sigma$,...
0
Here is a proof that context-free languages in general, not only regular ones, are not closed against making them prefix-free.
Bare with me, as I will try to make it as formal as possible.
We will demonstrate that:
Theorem 1. $NOPREFIX(L)$ are the $u\in L$ such that no proper prefix of $u$ is in $L$. Context-free languages are not closed under $NOPREFIX$...
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.
...
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 ...
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)
...
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-&...
0
Why there is no way to write "permutation of" in Regexes
A permutation of a regular, infinite language (infinite amount of words) is not necessarily regular. Thus, it can't be written as regex.
Proof
Think of of the language (ab)*. (Example inspired by David Richerby.) One of its permutations is a*b*. This is not a regular language. qed.
Top 50 recent answers are included
