# 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 ...

48 views

### Proving two languages are equal

Q: Show that $\{a,b\}^* = \{a\}^*(\{b\}\{a\}^*)^*$. I am aware of the fact that both sides are sets, infinite sets actually. So for example showing that both sides are subsets of each other would ...
40 views

### How to check whether arbitrary finite [syntactic] monoid is aperiodic or not?

Does there exist an algorithm to decide whether a (finite in my case) syntactic monoid is aperiodic or not? By definition, a monoid is aperiodic if for each $x$ from monoid there exists an $n$ with ...
49 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$, ...
24 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.
18 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 ...
32 views

### Is there a language like L in which $\overline {L^*} = \overline L^*$?

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 ...
87 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 ...
25 views

### How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_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$, ...
31 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. ...
41 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 ...
31 views

### Subtracting a context-free language from a regular language

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 ...
21 views

### confusion of an example for Powerset construction

I have an example of Powerset construction from the lecture. Powerset construction is applied on automata A1. The result is automata A2. You could see I do Powerset construction myself below the ...
86 views

### Is the set of languages over an alphabet Σ missing k words from Σ* countable?

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is ...
72 views

### What is so special about categories that lead people to use them to “formalize math”?

There are countless interesting structures - lists, trees, maps, graphs. Yet, categories - which, if I understand, is just a graph with some constraints on its shape - are apparently special somehow, ...
30 views

### Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
23 views

### Reverse of binary number

Let us say that x is a set of binary numbers $$x = \{0, 1, 1001\}$$ Am I correct that $x^R$ is equal $$x^R = \{0,1,1001\}$$ or is it: $$x^R = \{1,0,0110\}$$ What I mean by that is: do we create a ...
19 views

94 views

### Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
60 views

38 views

122 views

### Stuck on GEB chapter 9 - is b a MU number? is b a TNT number?

I'm reading through Gödel, Escher, Bach, and I found myself stuck at chapter 9. I've been rereading through several times already, but I must be missing something. To clarify my background, I'm a ...
25 views

### when do we say a grammar to be unambiguous with respect to parse tree and derivation tree?

In normal terminology we say that both the parse and derivation trees are same in meaning so if a grammar derives one string with left derivation as well as right derivation then it is ambiguous , if ...