New answers tagged automata
1
You can actually do it in at most $n+1$ queries. Just first check that the whole sentence is satisfiable, then play guess-and-check for each variable. Writing $|\phi|$ for the number of variables in the sentence $\phi$,
$$\mathit{cnf\_and\_sat}(\phi)=\left\{\begin{align*}
&\mathit{cnf}(\phi,|\phi|)&\mathit{sat}(\phi)\\
&\mathbf{unsat}&\mathrm{...
1
First of all, check whether $\phi$ is satisfiable using $M$. If it is, you can find a satysying assignment as follows:
For each variable $x$ of $\phi$ do the following:
Set $x$ to true. Simplify $\phi$ to remove $x$ (if a clause contains $x$ then you can delete the clause, if a clause contains $\overline{x}$ then you can delete $\overline{x}$ from the ...
1
If you want to decide whether a CNF formula is satisfiable or not you can simply decide it with one invoke of $M$ on your formula.
But if you want to calculate its satisfying assignment, your problem is a search problem not a decision problem. To do that you can simply invoke $M$ on $\phi [True/x_i]$ (substituting variable $x_i$ with value $True$) for each ...
5
$G_1$ and $G_2$ are equivalent if and only if $L_{G_1} = L_{G_2}$.
Since the relation $=$ is an equivalence relation over languages, so is the equivalence between grammars.
1
Let $\mathcal{G}$ be the set of all context-free grammars and let $\rho \subseteq \mathcal{G}^2$ denote the binary relation "being equivalent to".
Let $G$ be a CFG grammar. Clearly it holds that $G \rho G$ since $L_G=L_G$. Therefore $\rho$ is reflexive.
Let $G$ and $G'$ be CFG grammars such that $G \rho G'$. By definition of $\rho$ we have $L_{G} = ...
3
"$\lambda$" is commonly used to represent the empty string, although "$\epsilon$" could be the more common one.
This was introduced earlier in that book, section "3.1 Grammar Editing" of chapter "Regular Grammars".
On the last row you will enter the production $A \rightarrow \lambda$, a
$\lambda$-production. To do ...
2
Every rational language can be represented by (at least one) rational expression, and every rational expression represents a rational language. That means for any rational language, you can find the equivalent expression (though it might not always be a simple task). In fact, there are algorithms that convert any NFA into an equivalent rational expression ...
0
The first DFA is correct, and the second is incorrect. When we say a string ends in 00 we imply that it must have at least two characters. So, it can't be the empty string, and it also can't be the single 0 string.
This dfa should accept all binary divisble by 4. But how is nothing(it is not zero mind that) divisible by 4?
I agree, and this is a good way ...
4
Yes. What you are constructing is the product automaton recognizing the language $L_{s,q}\cap L_{q,f}$, where for $q, q' \in Q$, $L_{q,q'}$ is the language of words leading from state $q$ to state $q'$. Formally:
$$L_{q,q'} = \{u\in \Sigma^*\mid q'\in \delta^*(q, u)\}$$
It is well known that $L_{q,q'}$ is a regular language (just consider the initial state $...
-1
a* means that "a" must occur zero or more times.
a+ means that "a" most occur one or more times.
In other words, a* allows an empty string, while a+ doesn't (unless a itself allows an empty string).
To write it: If your editor allows it easily, $a^*$ and $a^+$ are preferable, because they are correct. On this site: Dollar, a, caret, star, ...
0
This will accept any word containing $a$ or $b$. There's a simpler way of describing the set of all words accepted by the FA, by the way. Can you see it?
5
Usually that is a matter of taste. If I am nathematically motivated then I write $a^*$ like some single argument postfix operations in mathematics. If I keep close to applications, I would type $a*$ because typing superscripts in input for programs seems silly.
Same for $a^+$.
Be aware that in the context of regular expressions plus $+$ might have another ...
0
You can basically follow the same reasoning without explicitly constructing the resulting finite automaton, using closure properties instead. That might save a lot of technical details. And it makes states $p,q$ explicit, rather than remembering them in states.
Given $X=(Q,Σ,δ,s,F)$ the DFA for $A$, now consider some derived automata that only change initial ...
0
The generic "theoretical" construction starting from a non-deterministic automaton with state set $Q$ introduces all subsets of $Q$ to be the states of the DFA. This wil introduce many states (subsets) that are nor reachable from the initial states. These states do not contribute to the language, so they can be omitted. From a theoretical point of ...
1
You missed state $\emptyset$. The transition from state $1$ when character $a$ is read goes to $\emptyset$.
Since all transition from $\emptyset$ also go to $\emptyset$, you can also use the standard convention of omitting $\emptyset$ (and the transition for character $a$ from state $1$).
If a DFA has some missing transitions, it can always be completed by ...
3
You certainly don't need a context-sensitive grammar to solve this problem (and it probably wouldn't help you, either). In fact, you can solve it with the precedence declarations available in most standard parser-generating tools. For example, a simple bison grammar is:
%left '+'
%left LAMBDA_LEFT
%left APPLY "lambda" VALUE ID '('
%%
expr : expr '+'...
0
Here's an idea to construct such a DFA. Consider differently the two parts of the language: $L = L_1 \cap L_2$ where $L_1 = \{u\in\{a,b\}^*\mid |u|_a \equiv 0 \mod 3\}$ and $L_2 = \{ubabbabv\mid u,v\in \{a,b\}^*\}$.
Note that I reworded "being divisible by $3$" into "being equal to $0$ modulo $3$". This will help to contruct the automaton....
0
"Function of the size of the input" when refering to time, means that the time an algorithm needs to run (that is, the algorithm's complexity) depends on the the number of elements of the input you give to the algorithm.
For example, the complexity of
Input: An array of integers of size n, named arr[n]
for (i = 0; i < 4; i++) return arr[3];
is ...
0
When we talk about things like Big-O notation for time or space complexity, the result is a function. We say that when a function takes in a value, it is a function "of" that value. (In other words, mathematical functions written $f(t)$ are said to be functions of time or functions with respect to time.)
In this case, we are making a function ...
4
$\Sigma$ is a (not proper) superset of itself but there are other supersets of $\Sigma$. For example if $\Sigma = \{a,b\}$ and $\Sigma'=\{a,b,c\}$ then $\Sigma'$ is a (proper) superset of $\Sigma$.
To show that the claim is true you just need to show that, for every finite set $\Sigma' \supseteq \Sigma$, you have $(\Sigma')^* \supseteq \Sigma^*$. Then, for ...
0
While reading prefixes $u$ of a word $w$, you need to count $|u|_a - 2|u|_b$ and check whether this value is greater or equal to $1$ when $u = w$.
Counting only the value of $|u|_a$ is easy: when you read a $a$, push a $A$ in the stack. The number of $A$ in the stack will be the same as $|w|_a$ at the end.
Counting only the value of $-2|u|_b$ can be done ...
1
A good first step for designing automata is to think about what states you will need. Here, you would need to remember the sum – which is not possible with a DFA – but thankfully, we only need to remember the sum in mod3 arithmetic, which means it can only have three distinct values: 0, 1 or 2. Therefore, we can keep track of the sum mod 3 with a finite ...
1
Your DFA doesn't match the empty string.
Note that if $L$ is regular, then infinitely many DFAs accept $L$. There is no unique answer for "DFA that accepts $L$". However, there is a canonical answer: there is a unique DFA with the minimum number of states that accepts $L$, known as the minimal DFA. Your teacher drew the minimal DFA for your ...
Top 50 recent answers are included