Skip to main content

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 generate them.

Filter by
Sorted by
Tagged with
0 votes
0 answers
29 views

Construction of a Finite State Automaton given a grammar

I have been studying formal language and automata theory from Mathematical Methods in Linguistics (Partee et al.). Specifically, I have been learning about finite state automata, formal languages, and ...
blanchietz's user avatar
1 vote
0 answers
45 views

State Diagram in Finite State Machines

This question is in Grimaldi's book: Let $I$ = $o$ = {0, 1}. Construct a state diagram for a finite state machine that recognizes each occurrence of $1010$ in a string x $\in$ $I^*$. (Here overlapping ...
winter's user avatar
  • 63
2 votes
0 answers
38 views

Question about $B^{+}$

This question is in Grimaldi's book: For $\Sigma$ = { x, y, z } , let A,B, $\subseteq$ $\Sigma^*$ be given by A = {xy} and B = {$\lambda$, x}. Note: $\lambda$ is the notation of the empty string. ...
winter's user avatar
  • 63
-1 votes
0 answers
18 views

L = { a^n b^m : n != m } - Matrix, Time varying, ordered and programming grammar

I would like help to prepare a thesis that will include: The language chosen, its description, its classification in Chomsky's hierarchy, Matrix grammar generating the language chosen in point 1. Time-...
Polymor's user avatar
0 votes
0 answers
44 views

Software language specification: null VS empty objects.

I have noticed that in software language specifications, there is pretty much always a NULL element and I am wondering if it is strictly necessary and how it maps to algebraic structures, given that ...
Barzi2001's user avatar
  • 253
3 votes
2 answers
186 views

Why does $\forall n \in \mathbb{N} \vdash P(n)$ not imply $\forall n \in \mathbb{N}P(n)$?

I am trying to understand why $\forall n \in \mathbb{N} \vdash P(n)$ doesn't imply $\forall n \in \mathbb{N}P(n)$ by studying the concepts in this answer, and had 2 questions about the difference ...
Princess Mia's user avatar
  • 3,019
1 vote
1 answer
129 views

Why do we need a metatheory if we can include self-referencing language in the object theory?

I am wondering why we need to have a metatheory in order to talk about a theory- why can't we just add self-referencing terms to the language of the formal system on which the theory itself is based, ...
Princess Mia's user avatar
  • 3,019
2 votes
2 answers
83 views

How to prove surjectivity? If $\mathcal{A}$ is an alphabet, then the set $W$ of all words from $\mathcal{A}$ is countable.

I'm trying to prove that If $\mathcal{A}$ is an alphabet, then the set $W$ of all words from $\mathcal{A}$ is countable. In resume I'm kind of using the Gödel enumeration. I index all symbols from $\...
Alejo's user avatar
  • 251
4 votes
2 answers
579 views

Formal language Concatenation is a binary operation?

In formal Language theory does the concatenation of two strings can be seen as a binary operation? If so, what are the domain and codomain? You might think that if given $\mathcal{A}$ alphabet then $W ...
Alejo's user avatar
  • 251
0 votes
0 answers
32 views

Proof in formal theory.

Axiom: $A \leq A$ Rules: $ \frac{A\leq C}{min(A,B)\leq C}$ $\frac{A\leq C; B\leq C}{max(A,B)\leq C}$ $\frac{min(A,B)\leq C}{min(B,A)\leq C}$ $\frac{A\leq max(B,C)}{A)\leq max(C,B)}$ $\frac{...
Danilo Jonić's user avatar
11 votes
1 answer
238 views

The “Pumping Lemma” For Finite Monoids

Let $M$ be a finite monoid. I’m trying to prove the following: there is a constant $N$ such that if $n \geq N$ and $m_1, \ldots, m_n \in M$, then some subword of $m_1 \cdots m_n$ is an idempotent. (...
neddo's user avatar
  • 205
2 votes
1 answer
52 views

Unclear evaluation of brackets in $\lambda$-Calculus

I have problems with evaluating this $\lambda$-Expression. $$(\lambda x.\lambda y.x(yx))\ (\lambda z.w)$$ The result should be, according to online calculators, $\lambda y.w$. But Iam really confused. ...
Flairo's user avatar
  • 77
2 votes
0 answers
57 views

How much notation should there be in a formal proof? Is there a general guideline?

I am writing a conference paper in formal language theory with an involved proof and I've found myself struggling with notation. In particular, I don't know when to favor notation and when to favor ...
JonasPK's user avatar
  • 31
0 votes
0 answers
44 views

Since axioms described using normal language, have this ever created problems?

People formalized mathematics using axioms. But axioms still need a natural language to describe them. Have inaccuracy of definitions, caused by using natural language in stating axioms, ever created ...
Den4ik's user avatar
  • 1
0 votes
1 answer
87 views

What's the behaviour of $\partial(q, a)=\emptyset$ on NFA?

Given an NFA say $N=(Q,\Sigma, q_0, \partial, F_Q)$, where $\partial: Q\times(\Sigma\cup\{\varepsilon\})\to\mathcal{P}(Q)$. It's confusing about the behavior of say $\partial(q, a)=\emptyset$ for any ...
linear_combinatori_probabi's user avatar
0 votes
0 answers
44 views

Decidability and Semi-Decidability of Languages Defined by Turing Machines

Let's define the input alphabet (A = {0, 1}) and the tape alphabet (T = {0, 1, B}). Let (U) be a universal machine. For a word ($w \in A^*$), we define the Turing machine ($M_w$) as follows: if (w) is ...
Weronika L's user avatar
0 votes
0 answers
31 views

Formalities on loop invariant - algorithms

When proving an algorithm using a loop invariant, we need to check these three things. The loop invariant holds before the loop is entered (initialization) If the loop invariant holds before the loop ...
Agustin G.'s user avatar
0 votes
0 answers
30 views

Why doesn't the following idea prove the statement "If $A_{1}, A_{2}$ are regular languages then so is $A_{1}+A_{2}$"

Theorem Why doesn't the following idea prove the statement "If $A_{1}, A_{2}$ are regular languages then so is $A_{1}+A_{2}$"(concatenation operation) Argument If one designs the automaton ...
Debu's user avatar
  • 1
0 votes
0 answers
58 views

Set theoretic definition of terms of the untyped lambda calculus

I am trying to translate the following definition (in Agda) of intrinsically scoped terms of the untyped lambda calculus into more mathematical (in particular set theoretical) notation: ...
user11718766's user avatar
0 votes
1 answer
49 views

What is the proof that $\{ \varepsilon \}^+ (Kleene plus) = \{ \varepsilon \}$ [closed]

So the proof that $\{ \varepsilon \}^* = \{ \varepsilon \}$ I understand, however I don't get why $ \emptyset ^+ = \{\} $ but $ \{ \varepsilon \}^+ = \{ \varepsilon \}$. because if the definition of $\...
calyorbro's user avatar
0 votes
0 answers
84 views

A question on binary strings and bit swapping.

I consider binary strings over the bit-alphabet $\{0,1\}$. A binary string $S$ is balanced if the number of occurrences in $S$ of the bit $0$ is the same as the number of occurrences of the bit $1$; $...
Nellina's user avatar
  • 11
0 votes
1 answer
49 views

Find the quotient of $L_1$ and $L_2$.

We want to find the quotient of languages $L_1$ and $L_2$. My question is what happens when the length of a word in $L_2$ is greater than the length of the word in $L_1$, for instance: $abc$ and $cc$. ...
winter's user avatar
  • 63
0 votes
0 answers
33 views

Regular expression for binary numbers

I need to find regular expression for strings representing binary numbers that are not less than 51. How can I do that? I can't find any pattern in their binary pepresentation.
regina's user avatar
  • 27
0 votes
0 answers
77 views

Turing recognizable, unrecognizable languages

What are examples of a a) language L such that both L and comp(L) are both unrecognizable b) decidable language D, and an unrecognizable language N, such that their union D ∪ N is decidable c) ...
Miras Shaltayev's user avatar
0 votes
0 answers
14 views

Estimating the minimal number of changes needed to fix a syntax error in "code"

I am wondering if there is an existing library that computes the following: Imagine I give you a [string of] code (e.g., Python or any other formal language specified with a grammar) with some ...
Daniel's user avatar
  • 2,670
0 votes
1 answer
31 views

DFA automatic unit of two languages

Greeting, I have problems understanding the assignment in the field of automata theory and formal languages. The task says: Construct a minimal DFA that accepts the following languages: It is ...
LogicNotFound's user avatar
0 votes
1 answer
50 views

Minimal DFA with language

I have a doubt about this task, have I done it correctly? The task is: Construct a minimal DFA that accepts the following language:
LogicNotFound's user avatar
2 votes
1 answer
75 views

How to prove $\{0,1\}^*$ equals $\{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^*\{0\}^*$

Consider the set of all binary strings which is $\{0, 1\}^∗$ Now I want to prove the following: (A) Prove that $\{0,1\}^* = \{1\}^* (\{0\}\{0\}^*\{1\}\{1\}^*)^*\{0\}^*$ (B) Prove that the elements of $...
DrTokus1998's user avatar
3 votes
1 answer
179 views

What exactly is a structure of a language?

I understand that structures are means by which we know how to interpret certain languages. So for example, in the language of number theory, we might have $\displaystyle L=\left\langle 0,S,+,\cdot,E,&...
Alice's user avatar
  • 508
1 vote
0 answers
37 views

Understanding the symbolism of Carnap's Language II [duplicate]

I'm reading a pretty old paper. The authors deem "the most appropriate symbolism [...] that of Language II of Carnap, augmented with various notations drawn from Russell and Whitehead, incuding ...
lafinur's user avatar
  • 3,468
1 vote
1 answer
64 views

Find $L_1$ and $L_2$ (formal languages)

We have two languages $L_1, L_2 \subseteq \{{a, b}\}^{*}$. According to the following formulas find $L_1$ and $L_2$: $L_1 = \{\lambda\} \cup \{a\}.L_1 \cup \{b\}.L_2 $ $L_2 = \{\lambda\} \cup \{b\}....
winter's user avatar
  • 63
1 vote
1 answer
31 views

What's the maximum possible compression ratio for different languages?

Given two alphabets $A=\{a_1, a_2, ..., a_n\}$ and $B=\{b_1, b_2, b_3, ..., b_m\}$, what is the maximum average compression ratio possible to achieve by bijectively encoding strings of B using strings ...
minseong's user avatar
  • 1,303
0 votes
0 answers
19 views

Construct the grammar that generates the given languange

Find a grammar that generates this language : L = { w : |w| mod 3 >= |w| mod 2 } over the alphabet sigma = {a} I tried and got the abstract logic . Length where mod 3 < mod 2 is length should be ...
RAGUL KARTHICK's user avatar
3 votes
1 answer
50 views

Finding a bound for existential quantification

Let $\Sigma$ be an arbitrary alphabet, $\mathcal{P}$ denote the set of all prime numbers, and $\omega := \mathbb{N} \cup \{0\}$ Take the following set. $$ L = \left\{ (x, \alpha, \beta) \in \omega \...
lafinur's user avatar
  • 3,468
0 votes
0 answers
25 views

Alternative approaches to a primitive recursion problem

Let $\Sigma$ an alphabet. We define the primitive recursive set as follows: $PR_{0}^{\Sigma}$ contains the succesor, predecessor, projection and constant functions. It also contains the $d_a$ function,...
lafinur's user avatar
  • 3,468
1 vote
0 answers
34 views

Designing a DFA with n States for Maximum L* Learning Rounds

I'm working on constructing deterministic finite automata (DFAs) with a specific learning complexity when using the L* algorithm developed by Dana Angluin. My goal is to create a DFA of size ( n ) ...
Coping Forever's user avatar
1 vote
1 answer
126 views

Why is a set is decidable iff it is the domain of a computable function

I'm studying three paradigms of computability theory: Godel's, Turing's, and von Neumann's. In the first two, it is given as a theorem that $f$ is a computable function iff its domain $S$ is decidable ...
lafinur's user avatar
  • 3,468
2 votes
1 answer
45 views

Relationship between function decidability and set decidability

Let $\Sigma$ denote an arbitrary language. If $\omega = \mathbb{N} + \{ 0\}$, a $\Sigma$-mixed function is a function s.t. $\mathcal{D}_f \subseteq \omega^n \times \Sigma^{*m}$, with $n, m, \geq 0$, ...
lafinur's user avatar
  • 3,468
1 vote
1 answer
51 views

Proving that a Turing machine is deterministic using instantaneous descriptions

We define an instantaneous description of a Turing machine as a word $\alpha p \beta$, with $\alpha, \beta \in \Sigma^{*}$ and $q \in Q$, s.t. if $$ d = \alpha_1 \ldots \alpha_n q \beta_1 \ldots \...
lafinur's user avatar
  • 3,468
1 vote
0 answers
46 views

Finding the primitive recursive characterstic function of a set

Context of the problem I think it is important to say that this is how predicate quantification is defined in my textbook: Let $\omega = \mathbb{N} + \{0\}$, $S_i \subseteq \omega, L_i \subseteq \...
lafinur's user avatar
  • 3,468
2 votes
1 answer
61 views

Mitchell Foundations for PL 2.3.4 (observational equivalence)

Background. The language is PCF, with observable types $\text{bool}$ and $\text{nat}$. $\text{eval}$ is the partial function on PCF terms such that $\text{eval}(M) = N$ iff $N$ is the unique normal ...
emesupap's user avatar
  • 698
1 vote
0 answers
84 views

Given an arbitrary language L is there an algorithm that terminates and decides whether the language is regular or not? [closed]

I have an arbitrary language $L$ (with finite amount of symbols $k$), assume the language can be represented in finite space as an input, you can also assume that we can check for $w\in\Sigma^*$ ...
Coping Forever's user avatar
0 votes
1 answer
37 views

Can someone explain to me what this transition means here: a, Z : AZ

Can someone explain to me what this transition means here: a, Z : AZ
sade's user avatar
  • 19
0 votes
0 answers
22 views

Undecidability of CFG subtraction under a co-finiteness assumption

Fix a finite alphabet $\Sigma$ for the entire discussion. There is a rather obvious proof that the difference of two context-free grammars $A$ and $B$ (compute the language $L(A) - L(B)$) is not ...
V0ldek's user avatar
  • 101
1 vote
2 answers
75 views

What can domain of discourse contain in FOL? [closed]

There are different interpretations for any FOL sentence. One of several things that we should specify when we choose some interpretation is domain of discourse over which we quantify. What is not ...
user341's user avatar
  • 157
0 votes
0 answers
34 views

Formal definition of string to string substitution in a string

This question is related to my previous one, here: Formal definition of string-to-term substitution. Let $A$ be a nonempty alphabet. Also, let $s$ be a nonempty string, and let $t$ be any string, ...
user107952's user avatar
  • 21.4k
0 votes
1 answer
83 views

How to prove that the set of theorems of any recursively axiomatized theory is a recursively enumerable set?

I read the article Craig's theorem written by Putnam (1965). I don't understand the claim on page 3 of the article: The set of theorems of $T$, where $T$ is any recursively axiomatized theory, is ...
유준상's user avatar
1 vote
0 answers
61 views

On the purpose of signatures in formal languages

I have a little doubt about the concept of signatures and their relationship with formal languages. Here are some definitions I'm using: An alphabet is a set of symbols. A formal language $\mathcal ...
Undefined user's user avatar
6 votes
1 answer
78 views

Equivalence relations, formal languages, and hypercube walks - what did I unleash on my students?

I teach a class in discrete mathematics and formal language theory. On my most recent final exam, I asked a question that involved a crossover between equivalence relations and formal languages. Here'...
templatetypedef's user avatar
1 vote
2 answers
161 views

Circularity in the argument that Gödel's incompleteness theorems undermine Hilbert's program

I'm only familiar with the very basics of mathematical logic, but over the last few days I have been looking into Gödel's incompleteness theorems and it seems to me (but I might simply be grossly ...
Inzinity's user avatar
  • 1,773

1
2 3 4 5
41