Tagged Questions
1
vote
1answer
113 views
Logical Conjunction of Binary Decision Diagrams
Compute a Binary Decision Diagram for $B1∧B2$. Furthermore, for an arbitrary BDD B you can use the equations $B∧F=F$, $F∧B=F$, $B∧T=B$ and $T∧B=B$.
To construct the BDD i start from the leaves ...
1
vote
1answer
29 views
Binary Decision Diagram of $(A\Rightarrow C)\wedge (B\Rightarrow C)$?
I made a Binary Decision Diagram for $(A\vee B)\Rightarrow C$, which i think is correct.
Know i want o make a Binary Decision Diagram for $(A\Rightarrow C) \wedge (B\Rightarrow C)$ but i can't. I ...
0
votes
1answer
26 views
Given a DFA $\mathcal{M} = (S, \Sigma, q_0, \delta, F)$, is there an algorithm that finds the pumping length of $L(\mathcal{M}$)?
This question has been bugging me for a while, and I'm curious what such an algorithm would look like, if it exists. My guess is that it does exist, but I'm not sure how it would look.
1
vote
0answers
13 views
Prefix relation on words in $\Sigma^*$ - why does a maximum element imply that the prefix relation is a linear order?
I'm currently preparing for a test, and I'm having trouble understanding one of the preparation questions. The question is as follows:
Let $\Sigma$ be a finite alphabet. The prefix relation on words ...
1
vote
1answer
40 views
Proof of algorithm refinement
I recently had an interview in which I was asked to produce an algorithm to that computes the pairs of integers, from a list, that add up to a integer k.
I then had to increase the time efficiency of ...
2
votes
1answer
73 views
Pumping Lemma problem
Apply pumping lemma to each of these and prove that they are not regular.
$L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$
$L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$
Here my ...
1
vote
2answers
91 views
Finite automaton that recognizes the empty language $\emptyset$
Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
4
votes
2answers
118 views
Push down automata problem
Informally describe the Nondeterministic PDA that generates:
$$\{x\#y\ \mid x,y\in\{a,b\}^{*}\text{and}\space x\ne y\}$$
My initial plan was to use nondeterminism to go through each character before ...
4
votes
1answer
43 views
Does the following transformation preserve context-freeness?
I encountered this problem involving manipulating a context-free language. Let $L$ be a context-free language. Define $L^{\#} = \{ x : x^i \in L$ for every $i=0,1,2,...\}$. Is $L^{\#}$ always ...
3
votes
2answers
186 views
Question about regular languages and finite automata
We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
1
vote
1answer
92 views
Proof of the pumping lemma for Context-Free Languages
I have a doubt concerning the proof of the pumping lemma for context-free languages. The pumping lemma for context-free languages is stated as follows:
If $A$ is a context-free language, then ...
3
votes
1answer
57 views
Explain why if the language A is recursive, then A is reducible to 0*1*
I'm in a theory of computation class and there is a problem that I think I am way overthinking.
Can anyone point me in the right direction with the following:
Give a short justification of the fact ...
1
vote
1answer
62 views
Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink
So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...
1
vote
1answer
86 views
How do you encode a programm in a category?
A Type-0 language (in the Chomsky hierarchy) is Turing complete and so you can encode all machines in them - you only need a compiler which translates it to the respective machine code. Appearently, ...
0
votes
1answer
175 views
Converting each formula into Conjunctive Normal Form?
How hard is it to translate an arbitrary well-formed formula into CNF formula? It seems it can get exponential in some occasions like $(a\wedge b)\vee (c\wedge d)$ is transformed into $(a\vee ...
0
votes
0answers
55 views
Confusion about proving equivalence of two states in FSM
There is this proof:
M = (Q,S,R,f,g). where Q is the set of states, S input alphabet, R output alphabet, f state transition function Q X S => Q, g output funtion Q => R
Suppose that q1, q2 are two ...
0
votes
1answer
80 views
Unbounded number of tapes of Turing Machine
Turing Machine with multiple tapes can be encoded such that its computational power is equivalent to Turing Machine with single tape. My question is if we have unbounded number of tapes, just like the ...
0
votes
2answers
279 views
Context free languages closure property $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$
I have been working on the following two problems:
1) Given any context free language L, form a new language by taking symbols at the odd positions, i.e. $w=a_1a_2\dots a_n \mapsto w'=a_1 a_3 a_5 ...
2
votes
1answer
110 views
Function problem vs. decision problem
Take the set $FP$ of number-theoretic functions that are computable in polynomial time. Let us restrict to those functions with range in $\{0,1\}$, $FP_{0,1}$. Is there any correspondence with ...
2
votes
1answer
70 views
Confusion related to context sensitive grammar
I have this confusion related to context sensitive grammar. I was referring to this article http://en.wikipedia.org/wiki/Context-sensitive_grammar. And it has given an example of production rules for ...
4
votes
3answers
129 views
Deciding equivalence of regular languages
Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows:
build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
2
votes
1answer
152 views
$L=\{\langle G_1,G_2 \rangle|G_{1,2}$ are context free grammars, and the size of $L(G_1) \cup L(G_2) $is a prime$\} \in R$?
Why does the following language $L=\{\langle G_1,G_2\rangle|G_1$ and $G_2 $are context free grammars, and the size of $L(G_1) \cup L(G_2)$ is a prime $\} \in R$?
How do I prove it? I didn't come to ...
3
votes
2answers
59 views
Does $L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ s.t when $M$ runs on $w$, $M$ visits some state at least $k$ times$\} \in R$?
I'd like your help with understanding , how come the following language is decidable (in $R$):
$L=\{(\langle M \rangle,k)| M$ is a TM and $\exists w\in \sum^*$ such that when $M$ runs on $w$, $M$ ...
0
votes
1answer
61 views
How to prove that the language of a DFA is some $L$
Consider the following DFA:
It is quite clear that the language of this FDA is all the words that don't have the word $aa$ as a subword.
My question is: How can I formally prove that this is the ...
0
votes
0answers
28 views
Is a satisfiable FOL-sentence a prime event structure always satisfiable in a regular trace event structure?
Suppose first-order logic sentence is satisfiable in the class of prime event structure. Is it also satisfiable in some regular trace event structure? (for all notions I'm referring to Madhusudan's ...
2
votes
1answer
104 views
Is the set of codes of Deterministic Finite-State Automata a regular language?
Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
1answer
66 views
A model of computation for co-CFLs?
The context-free languages can be described as the languages that can be generated by a context-free grammar or recognized by a (nondeterministic) pushdown automaton.
The context-free languages are ...
6
votes
3answers
126 views
Reductions for regular languages?
To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason ...
2
votes
4answers
2k views
Intersection of two deterministic finite automata?
I'm trying to solve a problem where I have to create a DFA for the intersection of two languages.
These are:
$$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
1
vote
1answer
95 views
Pumping lemma for regular “pumped formal language”
Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. We define
$$\verb+lmult+(L)=\left\{x^iu\;|\;x\in\Sigma,u\in\Sigma^*,i>0,xu\in L\right\}\cup\{\epsilon\}.$$
[...]
Show the ...
2
votes
1answer
144 views
Using pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular?
I'm trying to use pumping lemma to prove that $L = \{(01)^m 2^m \}$ is not regular.
This is what I have so far: Assume $L$ is regular and let $p$ be the pumping length, so $w = (01)^p 2^p$. Consider ...
0
votes
1answer
157 views
Proving that a grammar generates a language
Since every context free grammar is equivalent to a Push down automaton, to show that a grammar $G$ generates a language $L$, is it sufficient to draw a PDA equivalent to $G$ and then show the PDA ...
1
vote
3answers
156 views
Showing that two regular expressions represent complementary regular languages over {0,1}
How do up you show that two that the regular expressions, such as $(01+1)^*$ and $(0+1)^*\left(0 + 00(0+1)^*\right)$ represent complementary regular languages over $\{0,1\}$? I'm trying to do some ...
5
votes
3answers
311 views
An analog of the Myhill-Nerode Theorem for context-free languages?
The Myhill-Nerode Theorem gives an exact characterization of the regular languages. Given any language, one can check whether it meets the criteria of the Myhill-Nerode theorem to decide whether or ...
1
vote
3answers
212 views
Proving these are/are not regular
In my computing class we just finished studying regular languages. I didn't do as well as I had hoped on my work so I was wanting more insight on the correct way to go about these proofs. My ...
2
votes
1answer
174 views
Size bound on regular expression describing language of an $n$-state deterministic automaton
The class of languages that can be recognised by some deterministic finite automaton is the same as those described by some regular expression.
I evoked this well-known fact in class when discussing ...
0
votes
0answers
93 views
Converse of Gold's theorem and necessary condition for unlearnability
Background
A class of languages $C$ has Gold's Property if $C$ contains
a countable infinite number of languages $L_i$ such that $L_i \subsetneq L_{i + 1}$ for all $i > 0$
a further language ...
4
votes
2answers
246 views
A question on context-free languages from Sipser's computation book
I'm trying to learn some computability theory, and I came across a question in Sipser's book that I can't figure out. The exercise asks to show that there is an algorithm which will accept a ...
2
votes
1answer
138 views
Kleene closure over a formal language
Given a formal language L, is $L \subset L^*$ or is $L \subseteq L^*$?
To give context, I am tasked with proving whether or not there exists a language such that $(L^*)^c = (L^c)^*$. Assuming the ...
3
votes
1answer
141 views
Regular expressions which first disagree after an exponential length
Problem 8.24 of Sipser's Introduction to the Theory of Computation asks:
For each $n$, exhibit two regular expressions $R$ and $S$ of length $poly(n)$ where $L(R)\not =L(S)$, but where the first ...
2
votes
1answer
511 views
Nondeterministic PDA to Deterministic PDA
Are there any resources on how to convert a non-deterministic PDA to a deterministic one, if a deterministic PDA actually exists? Or is there a step by step way on how to do this, kind of like going ...
1
vote
0answers
352 views
Regular expression from DFA
I want to create a regular expression from the following deterministic finite automaton using an equivalence system:
$\begin{align}L_1 = & \{a\}L_1 &\cup& \{b\} L_2 & \cup & ...
3
votes
1answer
55 views
Equivalences of regular expressions - which one is wrong?
Let $\alpha,\beta \in \text{RA}(\left\{0\right\})$ where $RA(\Sigma)$
is the set of all regular expressions of the alphabet $\Sigma$.
The following two equivalences are given:
...
1
vote
1answer
106 views
Reduction over intersection of languages
Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$.
1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to ...
0
votes
2answers
92 views
What (formal) language does this describe? And, how do I prove it's regular?
I have this problem that I can't seem to be able to wrap my head around, and I was wondering if there was someone here that could help me understand it.
Let $L_1$ be a regular language over $\{a, b, ...
2
votes
4answers
118 views
Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?
Could someone please guide me how to go about solving this problem?
$$ baa \in a^*b^*a^*b^* .$$
The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any ...
5
votes
2answers
306 views
Regular Expression question
Notepad++ has a "regular expression" search but it does not implement the pipe OR | operator, which allows you to take two regular expressions and union them into ...
2
votes
1answer
349 views
Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$
Problem
Construct PDA that accepts the language $L = \{w_1cw_2 : w_1, w_2 \in \{a, b\}^*, w_1 \neq w_2^R\}$
For the language $wcw^R$, it's much easier because the stack is always empty after ...
1
vote
2answers
221 views
Pumping Lemma for inequalities
I have decided to teach myself formal languages and so I bought Peter Linz's Formal Languages and Automata. He presents the following problem (and many similar ones) in chapter 8 section 1, and I ...
1
vote
3answers
165 views
Do these two regular expressions $(a + b)^*$ and $(b^*a^*)^*$ generate the same language?
Are the languages generated by the regular expressions $(a + b)^*$ and $(b^*a^*)^*$ the same language?
The solution for this problem is yes, but I couldn't figure out why it is true. The first ...
