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
-2
votes
0
answers
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
1
vote
0
answers
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 ...
- 11
6
votes
1
answer
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 (). ...
- 71
1
vote
0
answers
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 ...
- 113
0
votes
1
answer
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....
- 3
0
votes
1
answer
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 ...
- 138
5
votes
1
answer
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
0
answers
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
2
answers
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 ...
- 4,697
0
votes
1
answer
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 ...
- 18.5k
0
votes
1
answer
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 "...
- 18.5k
0
votes
0
answers
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 ...
- 18.5k
0
votes
2
answers
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 ...
- 55
2
votes
0
answers
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 ...
- 21
1
vote
0
answers
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 ...
- 1,013
0
votes
0
answers
75
views
Is $x<y$ only meaningful if $x$ and $y$ are elements of the same set?
$x<y$ means that $x$ is less than $y$, but is it only meaningful/valid if $x$ and $y$ are elements of the same set?
$x<y$ iff $(x,y)\in<$ right?
$(x,y)\in<$ tells that the ordered pair $(x,...
2
votes
1
answer
38
views
Find the mistakes(pumping lemma proof). Can you help me?
There are pumping lemma proof. I have to find one mistake. Please help me [lemma proof][1]
- 21
1
vote
0
answers
33
views
Let 𝐿 be a regular language. Prove all minimal automata for the language are isomorphic
I have started to study formal languages, especially finite automata and regular languages and I encountered some difficulties, i.e. Is this true:
Automata will be called isomorphic if, by changing ...
- 95
0
votes
1
answer
42
views
Godel Theorem proof in algorithm theory
I am currently reading the Gödel's Incompleteness Theorem explained by Vladimir A. Uspensky. And I came across the following theorem which I think has contradiction with itself. Since I am a physics ...
- 43
0
votes
0
answers
34
views
Prove that if L is a recursive language, then its complement Ls is also recursive
Considering that a language $L$ is recursive iff there exist a Turing machine $T$ that accepts every string of the language $L$ and rejects all strings that don't match the alphabet of $L$.
In other ...
0
votes
0
answers
38
views
Creating "Zigzag" context-free grammar of $2$ languages with the same letters
Given are $2$ right-linear grammars, forming $L_1$ and $L_2$. The alphabet $T$ is the same for both languages, and $\epsilon$ (empty word) doesn't belong to any of the languages.
What is an example of ...
- 992
2
votes
0
answers
56
views
Prove that L = {$w∈${a,b,c}$^*$|w contains "abc"} is regular with Nerode theorem?
How to prove that $L = \{w \in \{a,b,c\}^* \mid w \text{ contains } abc \}$ is regular using the Nerode theorem?
Attempt
If I show that there are a finite number of equivalence classes for this ...
- 53
1
vote
1
answer
56
views
Recalling a theorem from vague memory: A monoid, in some sense, cannot "describe" the language (over one letter?) of words of prime length.
It has been over a decade (already!) since I studied a module on formal languages & automata during my undergraduate Mathematics degree. In considering a few things in combinatorial group theory (...
- 43k
0
votes
1
answer
50
views
Prove or disprove that L = {$a^nb^m$ | $m ≠ 3n + 5$} is a regular
How can I prove or disprove that $L = \lbrace a^nb^m$ | $m ≠ 3n + 5 \rbrace$ is a regular language?
Attempt
Assume $L$ is regular, then its complement $L^\complement$ is also regular.
$L^\complement ...
- 53
1
vote
0
answers
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 ...
- 11
2
votes
0
answers
21
views
Algorithm for computing the collection of all string homomorphisms $f$ such that $f(s) = t$ for fixed strings $s,t$
I'm coding on a website in Django so all my code will be implemetned in Python.
Anyway, I'm interested in the most efficient algorithm to compute the following problem.
Given input strings $s = ...
- 21
1
vote
1
answer
38
views
How can I determine the language from a DFA?
I was given three DFAs to solve.
I understand the first one is a*. I think the second one would be b*(a+)*.
I cannot figure out what the third one would be, it seems like there are too many different ...
- 11
0
votes
0
answers
23
views
Structural induction proof of substitution using semantics from "While" language
Hello I am currently self-studying the book "Semantics with applications: An Appetizer" and I don't know if I've gotten the right base case for the problem below:
Prove that $\mathcal{A} [[ ...
- 11
0
votes
1
answer
43
views
Proof by induction verification: $A\subseteq B$ implies $A^+ \subseteq B^{+}$
I tried the following induction proof:
$\sum \neq \emptyset$
$A,B \subseteq \sum^{*}$
$A^{+} := \bigcup_{n\geq 1} A^n $
$A^{n} :=$ "$n$-wise-concatenation of $A$ to itself"
$AA := \{ab | a \...
2
votes
1
answer
204
views
Is L = { words such that the maximum number of as following a b is equal to the maximum number of bs following an a} context-free?
Consider the language $L = \{w \in \Sigma^* \mid $ the maximum number of a's following a b is equal to the maximum number of b's following an a$\}$ over the alphabet $\Sigma = \{a,b\}$. So for example ...
- 121
2
votes
1
answer
206
views
What *is* a geometric formula?
In logic (and categorical logic) one learns that infinitary logic is like finitary logic, only that the formulas may contain set-indexed disjunctions and conjuctions such as $\bigvee_{i\in I}\phi_i$. ...
- 3,887
0
votes
1
answer
76
views
Construct Context-Free Grammar for $\{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$
One of the tasks on my exam was to construct a context-free grammar for the language:
$$L = \{a^ib^jc^kd^l : i,j,k,l\geq1\:\land\: i+j=k+l\}$$
I have no clue how to construct such a grammar, could ...
- 15
-1
votes
1
answer
51
views
How might we formally define the concatenation of two strings?
Below we offer some definitions of string.
How would you mathematically define the concatenation of strings?
The $\mathtt{HELLO\ WORLD}$ Example
$“\mathtt{HELLO}” + “\mathtt{\ }” + \mathtt{WORLD}” = ...
- 1,086
0
votes
1
answer
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$ ...
- 1,199
0
votes
1
answer
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 "...
- 3
0
votes
0
answers
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 ...
- 2,646
1
vote
0
answers
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 ...
- 295
4
votes
1
answer
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 ...
- 1,786
0
votes
0
answers
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$ ...
- 19
2
votes
0
answers
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 ...
- 18.5k
-2
votes
1
answer
56
views
Determining whether a given language is regular
Suppose language $L = \{\,a^{i} b^{k} : k \text{ divides } i\,\}$.
Some strings in $L$ include …
$\,a^{0} b^{1} = b \in L\,$ since $1 \text{ divides } 0$
$\,a^{1} b^{1} = ab \in L\,$ since $1 \text{ ...
- 151
1
vote
1
answer
61
views
Proving a class of languages is closed under union when it closed under concatenation, (inverse) homomorphic images, and intersections.
Let $C$ be a class of languages closed under concatenation ($\cdot$), intersection, homomorphic images, inverse homomorphic images, and intersection with regular languages. Prove that $C$ is also ...
- 2,214
1
vote
1
answer
43
views
Constructing context-free grammar
Construct a context-free grammar generating:
$$\{w\# wR \# | w \text{ is a string of one or more 0s and 1s, and a } \# \text{ is between w and its reverse, and a } \# \text{ is at the end}\}$$
The ...
- 37
0
votes
0
answers
36
views
What is the language generated by this grammar?
S → 0A | 1B | ɛ | 0
A → 0A | 0S | 1B
B → 1B | 1 | 0
I've tried to find some specific properties of some of the generated words, but I've failed.
- 37
3
votes
1
answer
66
views
Given a transitive and faithful permutation group $G$, is each set of syntactically transitive permutations connected by another permutation in $G$?
$G$ is a permutation group of degree $n \geq 4$ which acts transitively and faithfully on a set $X$ with $|X| = n$.
Given indices $i < j < k \leq n$, elements $\alpha \neq \beta \neq \gamma \in ...
- 317
0
votes
0
answers
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 &...
- 11
0
votes
0
answers
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 ...
- 63
9
votes
1
answer
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 ...
- 300
-1
votes
2
answers
69
views
Proving Language is Non Regular Using Pumping Lemma
I am working on a question where 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, ...
- 63
2
votes
1
answer
80
views
Unsatisfying proof for NP-Problems
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 $\...
- 438