# Tagged Questions

30 views

### Smallest grammar problem on a single character.

Let the alphabet be $\Sigma = \{a\}$. Say $s = a^6 = aaa aaa$. If the repeated variable $A = aa$ appears $k$ times in the expanded starting rule of a smallest grammar $G_s$ for $s$. Then that ...
47 views

### recursive definition odd length strings

Given the alphabet {aaa bbb}, give a recursive definition for the language that only contains odd length strings. must be constructive definition we are suppose to treat aaa as one letter and bbb as ...
19 views

### The max number of repeats of substrings of a sample of a language.

So we suspect that finding the smallest grammar of strings in the language $\{a^n : n \in \Bbb{N}\}$, is hard. But luckily as far as applications to natural language processing, we would rarely ...
20 views

### Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
94 views

### Mathematical concept for formal languages

A formal language is defined as a subset of finite-length strings over an alphabet. It is similar to the mathematical concept "relation", but the lengths of its strings are not fixed. Since the name ...
17 views

### not understanding the part of the answer for drawn turing machine

Could someone please tell me what does capital B mean here ? of course I know R and L stands for right and left... and also I know for example if we have a,b,R (which tells you if you have an a , ...
45 views

### My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
65 views

### how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
21 views

### (L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
128 views

### Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
54 views

### Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
58 views

### Prove the following by using mathematical induction

If we define the alphabet such that $$\Sigma = {\{a,b}\}$$ and let $w$ be a string over it. I'd like to prove $$( \operatorname{comp}(w))^R = \operatorname{comp}(w^R)$$ where $$w^R$$ and ...
56 views

38 views

### Mapping reduction to show NeverHalt is undecidable

I need help with showing that $NeverHalt_{TM} = \{\langle M\rangle|M\text{ is a TM which runs forever on every input$w$}\}$ is undecidable by giving an explicit mapping reduction. To show that a ...
30 views

113 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 ...
509 views

158 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 ...
66 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$ ...
### 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 ...
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 ...