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

67 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 ...
68 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, ...
22 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 ...
37 views

### Why is a the right answer? [on hold]

[ I dont understand Why a is the answer? Why is c NOT?
18 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 ...
16 views

47 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) ...
41 views

36 views

50 views

### How to prove whether a language is decidable and/or semi-decidable (or neither) using reduction?

I think I understand the basics of reduction, however I'm far from confident with using the techniques. I have a couple of examples that I'm struggling with: L1 = {< M > | M accepts an infinite ...
98 views

### What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
23 views

### Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
49 views

### Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be ...
58 views

### Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
24 views

### Checking if Post Correspondence Problem has a Solution

I have the following problem I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?
### For a regular language $L$, $Z(L)=\{x \in \Sigma ^* | \exists w \in \Sigma^*, xww\in L \}$, Is $Z(L)$ regular?
I was able to prove it is regular by induction on the length of the regular expression of $L$. I was wondering if there is a better way to prove it. Better in the way that it is not "Induction ...