# Tagged Questions

Formal languages are studied in computer science and linguistics. They are usually defined using various types of grammars (e.g. regular, context-free) and automata (e.g. deterministic and pushdown automata, Turing machines). There is a hierarchy of formal languages, which is based on the type of ...

77 views

### How to formalize a variable-binding operator, such like $\frac{d}{dx}$?

How to formalize a variable-binding operator, such like $\frac{d}{dx}f(x)$? For instance, I think we should treat $\frac{d}{dx}$ as a higher-order function of $x$, returning a function that takes it ...
59 views

### Decidable and Recognizable

I'm trying to work on this problem but I cant seem to find an approach to it: For any language L ⊆ Σ∗ define the language PREFIX(L) := {w ∈ Σ∗ | some prefix of w is in L} (a) Show that if L is ...
37 views

32 views

### Is there a concept of distance between number of steps needed to move from one step to another?

Let's say that we have a set of rewrite rules: $$AB \mapsto AC, A \mapsto B, B \mapsto A$$ Given the two strings $ABC$ and $BCC$ we know we can rewrite $$ABC \mapsto ACC \mapsto BCC$$ We can ...
22 views

### turing machine decidable description for the language

L = { | R is a regular expression that produces at least one word in {a, b} * which contains a symbol exactly 3 times} ...
38 views

### turing machine decidability language

I must show that this language is decidable but I think it's not {D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ } Here what I think I give a reduction from E(TM). I suppose that this ...
28 views

34 views

### Existence of context-free grammar over {0,1} alphabet

Is there a context-free grammar $G$ for which $L(G) = \lbrace w \in \lbrace 0,1 \rbrace^{*} : \exists a,b \in \lbrace 0,1 \rbrace^{*} \wedge w = aba \wedge |a| = |b| \rbrace$? This question could be ...
32 views

### Context-free language

Given $L= \lbrace w \in \lbrace 0, 1 \rbrace^* \ : \ |w|_0 \leq |w|_1 \leq 2 |w|_0 \rbrace$, where $|w_0|$ is number of zeros in $w$. Is $L$ context-free?
45 views

### Construct a regular expression for a given language

I'm currently working on some exercises to get used to create regular expressions from given languages and i'm stuck with a fairly simple exercise. So could you please tell me how to construct it step ...
23 views

### Language of binary multiplications relation.

Given $\Sigma = \lbrace 0, 1 \rbrace$ and $L \subseteq (\Sigma \times \Sigma \times \Sigma)^*$. Let $first(w), second(w), third(w)$ be word from $(\Sigma \times \Sigma \times \Sigma)^*$ limited to ...
102 views

40 views

68 views

### Prove concatenation of strings is associative

Q: Prove, using the definition of concatenation given in the text, that concatenation of strings is associative. DEFINITION: The concatenation of strings $x$ and $y$, written $x \circ y$, or ...
29 views

### How can I interpret a multiply-quantified statement?

∃ x ∈ R such that ∀ y ∈ R, x + y = 0. Can anyone help me rewrite this statement in plain english without symbols or variables? So far I have "There exists a real number whose number and other number ...
18 views

### What is the automaton recognising the language generated by G?

Why is B not accepted as an answer?: S --> 0A A --> 0A A --> 1B B --> 1B B --> e Which ends up in the state of the automata is in the accept state.
21 views

### What is the Right Context of a Word in Formal Langauge Theory?

I am reading this paper and am unable to understand this notation in section 2.2 - The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The ...
Assume that for every language L over the alphabet $\Sigma$, we define $L^*$ , $\overline L$ , $\Sigma^*$ & $L^n$ like this : $L^n$ means joining L to itself n times. For an alphabet like $\... 1answer 107 views ### Stronger Pumping Lemma for Context Free Languages Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ... 1answer 28 views ### How to identify context free language? Consider the following context-free grammars$:G_1: S → aS|B, B → b|bBG_2: S → aA|bB, A → aA|B|ε, B → bB|ε$Which one of the following pairs of languages is generated by$G_1$and$G_2$, ... 1answer 43 views ### Identify language of given PDA? Consider the transition diagram of a PDA given below with input alphabet$Σ =\{a,b\}$and stack alphabet$Γ = \{X,Z\}. Z$is the initial stack symbol. Let$L$denote the language accepted by the PDA. ... 1answer 54 views ### Reduction to/from REC and RE language? Let$X$be a recursive language and$Y$be a recursively enumerable but not recursive language. Let$W$and$Z$be two languages such that$\overline{Y}$reduces to$W$, and$Z$reduces to$\overline{...
I have the language $L=\{a, bb\}^*-\{a^ib^i|i\geq1\}$ and I have to show that $L$ is context-free. The first language is Regular, if I'm not mistaken, and the second is a well known context-free ...