# Questions tagged [formal-languages]

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 grammars and automata which can be used to generated them.

1,953 questions
Filter by
Sorted by
Tagged with
21 views

### Can anyone prove when this becomes true: A* - {x} = A^+; where A is a language on the alphabet sigma = {a,b}, and x belongs to sigma* [closed]

where A is a language on the alphabet sigma = {a,b}, and x belongs to sigma*
1 vote
37 views

### Signature homomorphism, but a single symbol can map to a composition of symbols?

Given two signatures $A$ and $B$, the regular definition for a homomorphism $A \to B$ maps (function/relation) symbols to (function/relation) symbols of the same arity. I'm looking for a weaker kind ...
195 views

### ((())()) is a theorem of PR?

If we have the following formal system, called PR whose formulas are strings of well-formed parentheses. The language has two symbols '(' and ')'. Any expression is a formula. The only axiom is (). ...
1 vote
55 views

### Decidable formal language with a finite but non-computable size

I'm looking for a formal language that has the following properties: Contains finitely many words (and you can prove it). Decidable/recursive (there's a Turing machine that always halts, that can ...
70 views

### Proof for halting problem is recursively enumerable

So, I know the proof for Halting Problem is not recursive using diagonalization. We prove it using proof by contradiction. First we assume HP is recursive which implies there is a Total Turing Machine....
27 views

### Generating functions of ambiguous regular languages are still rational?

The Chomsky-Schützenberger theorem states that any context-free unambiguous language admits an algebraic generating function. For unambiguous regular languages, the generating function is always ...
131 views

### An overview of mathematical-logical approaches in formalizing natural languages

Crossposted on MathOverflow I am an undergraduate mathematics student with a keen interest in pursuing research in the formalization of natural languages (from a more mathematical-logical approach), ...
1 vote
59 views

### What exactly does "a sufficiently expressive procedure for enumerating theorems" mean in the context of the incompleteness theorems?

Whenever I Google to try to find an actual formal statement of the first incompleteness theorem (as opposed to all the oversimplified explanations that talk about "true but unprovable theorems&...
1 vote
80 views

### Is the deducutive apparatus of a formal system necessarily a set of inference rules?

In the book "Logic" by Paul Tomassi, the author uses the term deductive apparatus to refer to the set of inference rules in propositional logic and first-order logic. The use of this term ...
31 views

### How to ensure uniqueness of readability of nested lists over some alphabet $S$?

Here is something that has been bothering me. Let me just give an example to show what I mean. Consider the alphabet $\{a,b,c\}$. $(a,b,c)$ is a list from this alphabet. $(a,b,(a,b))$ is a nested list ...
27 views

### Formal definition of "unnesting" a nested list.

This is very much related to my previous question on the iterated Kleene closure, here: The iterated Kleene closure of an alphabet. Someone in the comments called elements of my construction "...
40 views

### The iterated Kleene closure of an alphabet

The Kleene closure of an alphabet $A$ is the set of all finite sequences with terms in $A$. However, I am interested in defining something like an "iterated" Kleene closure. Let me give an ...
33 views

### Let $L \subseteq \{a,b \}^*$ be a rational language. Show that $K$ is rational.

Let $L \subseteq \{a,b \}^*$ be a rational language. $K$ the subset of words in $L$ that does not have has a factor $a^2$ and $b^3$. Show that $K$ is rational. If $A$ is a DFA that accepts L. I ...
33 views

### How do I prove that $L = \{a^{i}b^{j}a^{k} | i ≠ j, j ≠ k, k ≠ i ; i, j,k > 0\}$ is not context free?

It's not an assignment question, but I'm trying to prove that L is not context free. L = {a^i b^j a^k | i ≠ j, j ≠ k, k ≠ i ; i, j,k > 0} Edit: Thanks for ...
1 vote
62 views

### Not wanting to express the Gödel number of the actual string

Let's say I have a string of $n$ symbols, each with a Gödel number denoted $\ulcorner s_x \urcorner$, where the $x$ denotes that it is the $x$th symbol in the string. The Gödel number of the entire ...
75 views

1 vote
26 views

### How to create grammar that generates language $L = \{ w \in \{a, b, c\}^* | \#_a(w) = \#_b(w) \cdot \#_c(w) \}$

I want to know how to create CSG (context sensitive grammar) that generates this language $L$. My idea is that every time when adding another b, add as many a's as the word contains c's and vice versa ...
21 views

43 views

62 views

### Common divisor of a string exists if $A \cdot B = B \cdot A$

Let $A,B$ be nonempty strings over some finite alphabet and let $\cdot$ denote the concatenation operator. Let $s^{k}$ denote the string $s \cdot s \cdot s ... \cdot s$ concatenated itself exactly $k$ ...
50 views

### Build automata for words with both "bab" and "abb"

I have two finite automata, one for words containing "bab" and one for words with "abb." I wish to build automata that represent the multiplication of both (words with both "...
17 views

### Complementing and intersecting cones in $\mathbb{N}^d$

I'm trying to get further clarity on the proof that the semilinear sets (https://en.wikipedia.org/wiki/Generalized_arithmetic_progression#Semilinear_sets) are closed under complementation, starting ...
1 vote
125 views

### Proof of sentence "A language L is context-free if and only if L is accepted by a pushdown automaton."

I have the proof below in my lecture. I would be very grateful if someone could explain the argumentation for the case $\alpha = BC$. Furthermore, I do not fully understand the subsequent arguments ...
159 views

### Reasoning in natural language vs. reasoning in formal language

In ZFC set theory, we first used axioms to prove the existence of the set of natural numbers based on its definition, and after proving uniqueness, we introduced $\mathbb{N}$ in a new symbolic system ...
17 views

### Show that X is decidable in constant time when X is decidable in time less than n

I have a question about the following exercise: Let $X$ be a language decidable in time less than $n$, in other words there exists a DTM deciding $X$ that runs in time $f(n)$ where $f(n_0)<=n_0$ ...
52 views

### Formal definition of an algorithm that outputs the cardinality of a hereditarily finite set

Let our alphabet consist of three elements: the left brace {, the right brace }, and the comma $,$. Suppose we have already defined the language $L$ over that alphabet which represents the ...
56 views

28 views

### Simplification of Transition function in ω-automata (omega-automata)

Can someone explain the transition function in the below omega automata in the image along with the diagram? It's getting very tough for me to understand this. What I understood till now is that: If &...
53 views

### Proving Language is Non Regular With Pumping Lemma [duplicate]

I have the formal language $Z$ over the alphabet $Q \{a, b, c\}$ and it is generated by the context-free grammar whose non-terminals are $S, A$, and $B$, the start symbol is $S$, production rules are ...
278 views

### When does a semigroup homomorphism preserve identities on monoids?

Let $X,Y$ be monoids, with identities $e_X,e_Y$, respectively. Let $f:X\to Y$ be a semigroup homomorphism. That is, any function which satisfies $$f(xy)=f(x)f(y)\quad\forall x,y \in X\tag{1}$$ I know ...
One common strategy to prove that a problem or language $L$ is NP is to show that there exists a certificate $c$ which can be verified in polynomial time by a (deterministic) Turing machine. Let \$\...