Questions tagged [formal-languages]

Question 1

Contructions involving Godel-numbers allow a sufficiently expressive theory to talk about itself, i.e. there is a correspondence between sentences in the theory and sentences about the theory. There ...

Question 2

Let L be a language of first order logic. The generalization rule for universal quantifier says that, for $\phi\in L$, $\Sigma \vdash_L \forall x\phi(x) $ iff $\Sigma\vdash_{L\cup c}\phi([c/x])$, with ...

Question 3

I've got following statement (as a challenge, not as a hw or something), being told that it's kinda hard to prove it $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL Following statement (...

Question 4

I am studying Context-free Languages, and my professor gave as homework the following language $$ 0^a 1^b 0^c \quad where \quad a < b + c \quad and \quad a,b,c \ge 0 $$ My friend gave this answer: ...

Question 5

Fix a finite alphabet $A$. The set of regular languages is the smallest set of languages on $A$ (i.e. subsets $L$ of the free monoid $A^*$) containing $\varnothing$ and the singletons $a$ for $a\in A$ ...

Question 6

I am studying for exams, and previous years had these two problems that I have conflated in the title. Problem 1) For every regular language $ L \subseteq \Sigma^*$ over $\Sigma$, $\mathcal{H}(L)$ is ...

Question 7

In this problem $\Gamma(L)$ is defined as $\Gamma(L) = \{v \in \Sigma^* \mid \exists w \in \Sigma^*.(|v|=|w| \land vw \in L\}$ which I understand as: The set of all strings $v$ such that there exists ...

Question 8

I'm a noob trying to learn Godel's proof, and it seems that a large part of it relies on constructing a bijective mapping between the natural numbers and the set of all possible mathematical ...

Question 9

I understand what needs to be done in this problem and I had no problems with groups. I got that the variety consists of direct products of groups $\mathbb{Z}_{2}$, and the set of identities from the ...

Question 10

In Chapeter 3 of Speech & language processing, Jurafsky says "We need the end-symbol to make the bigram grammar a true probability distribution. Without an endsymbol,instead of the sentence ...

Question 11

A alphabet system has three letters C, A, T, and two words are equivalent if the following subwords can be inserted and deleted for a finite number of times such that the two words become equal: CC, ...

Question 12

This question is meant as a follow up of the previous question Link. Suppose now the string consists of numbers 1,2,3,4. The insertions and deletions allowed for an equivalence class is 11,22,33,44,...

Question 13

Problem: A string of numbers consists of 1, 2, and 3 only, with no limits on length. Two strings are considered the same if one can be transformed to the other with finite insertions or deletions of ...

Question 14

I'm trying to figure out why the lemma works for the context-free language: $L = \{ w ∈ \{a,b,c\}^* | \#_a(w) - \#_b(w) - \#_c(w) = 0 \}$ Say we choose $s=a^{2n}b^nc^n$, we can show that all the ...

Question 15

Im currently studying for an exam in theoretical computer science. Since I feel that it more belongs to mathematics than to practical computer science, I decided to ask here and not on stackoverflow. ...

Stack Exchange Network

Questions tagged [formal-languages]

What is philosophically the distinction between using a theory to study itself and Godel-like sentences?

Generalization rule for universal quantifier and extended language

Prove that $ L = \lbrace a^m b^n \mid m \neq n^2 \rbrace $ isn't CFL

How does this CFG enforce the inequality $0^a 1^b 0^c$ where $a < b + c$ and $a, b, c \geq 0$?

Constructions of regular languages

Prove that for every regular language/CFL $L \subseteq \Sigma^*$ over $\Sigma$, $\mathcal{H}(L)$ is also a regular language/CFL

Let $L_3 = \{a^nb^na^mb^m \mid n \geq 0, m \geq 0\}$. Give a CFG for $\Gamma(L_3)$

Is there a formal language where $\Sigma^*$ is uncountable? [duplicate]

Describe the variety of a) groups and b) monoids generated by $\mathbb{Z}_{2}$. Find a set $\Sigma$ such that $M(\Sigma)=V(\mathbb{Z}_{2})$.

Jurafsky Speech & language processing Chapter 3 "end-symbol to make the bigram grammar a true probability distribution"

Equivalent Words Using Given Operations

Counting Distinct Strings in Equivalence Classes

Counting Distinct Strings With Letter Deletion/Insertion Rules

Bar-Hillel Lemma Confusion ( Pumping lemma for context-free languages )

Regular expression with no same consecutive characters

Hot Network Questions