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.

Filter by
Sorted by
Tagged with
-3 votes
0 answers
23 views

Counterexamples to formal languages

Could you provide some simple Counterexamples that proof, next languages are not closed on its operations Lcf - intersection, complement Lcs - homomorphismus Lre - Complement
user avatar
0 votes
0 answers
18 views

Is there a s-grammar for $L_2=\{a^nb^m, n > m \ge 0\}$?

Define a simple grammar or s-grammar for $L_1=\{a^nb^n, n \ge 1\}$ is not difficult. $S \rightarrow aX$ $X \rightarrow aXB | b$ $B \rightarrow b$ How about this Language: $L_2=\{a^nb^m, n > m \ge 0\...
user avatar
-4 votes
0 answers
35 views

Prove the power between language and natural numbers

Prove the power equivalence of the language $L = \{\dots \text{def. of a particular language} \dots\}$ and the set of natural numbers $\mathbb{N}$. How to solve this type of tasks?
user avatar
0 votes
0 answers
30 views

Design a DFA for the language $L = \{a^n b \mid n \geq 0 \}$

Problem : Design a deterministic finite automaton for the language $L= \{a^nb \mid n \geq 0 \}$
user avatar
0 votes
0 answers
22 views

If $\mathcal{L}$ is regular, then prove that $\mathcal{L/3} = \{w ∈ Σ^∗|∃ x, y ∈ Σ^∗, wxy ∈ \mathcal{L}, |w| = |x| = |y|\}$ is also regular.

If $\mathcal{L}$ is regular, then prove that following language $$\mathcal{L/3} = \{w ∈ Σ^∗|∃ x, y ∈ Σ^∗, wxy ∈ \mathcal{L}, |w| = |x| = |y|\}$$ is also regular. $\mathcal{L/3}$ is the front $1/3$ ...
user avatar
5 votes
1 answer
111 views

Formalizing Natural Languages

I've been interested in the subject of metalanguages and how (if) we can formalize them. Most metalanguages I've encountered use some variation of a natural language (such as English, German or French)...
user avatar
-1 votes
0 answers
40 views

How do I prove $\leq_{T}$ is a symmetric relationship on $P(\Sigma^*)$

Does a reflexive and transitive Turing reducible relation on the powerset of all strings imply symmetry, too? Here is my understanding. If $\leq_{T}$ is transitive on $P(\Sigma^{*})$, then given $A \...
user avatar
0 votes
0 answers
60 views

Prove $ L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\}$ is a regular language where $L$ is regular [duplicate]

Let $L$ be a regular language with alphabet $ \Sigma $. Prove that the language $$ L' = \{uv \mid u,v \in \Sigma^*,\ vu \in L\} $$ is regular.
user avatar
0 votes
0 answers
24 views

Calculate nodes of the parse tree [closed]

Suppose that G is a context free grammar with productions that may have epsilon as the right side. If w is in L(G), the length of w is n, and w has a derivation of m steps, Show that a parse tree for ...
user avatar
  • 11
0 votes
0 answers
20 views

Is this a PDA for balanced parentheses language?

I have got following PDA: $A=(\{p, q\},\{0, 1\},\{Z\},\delta , p, Z)$ $\delta ( p, 0, Z) = \{(p, ZZ)\}$ $\delta ( p, 1, Z) = \{(p, \lambda)\}$ $\delta ( p, \lambda, Z) = \{(q, \lambda)\}$ Assuming ...
user avatar
  • 1
3 votes
2 answers
63 views

What does it mean for a language to be sparse?

A language $A \subseteq \sum^{*}$ is sparse, and we write $A \in SPARSE$, if there is a polynomial q such that, for all $n \in N$, $$\left|A \cap \sum^{n}\right|\leq q(n)$$ The definition of a ...
user avatar
1 vote
1 answer
31 views

Prove language irregularity using Nerode theorem

Let $L=\{b^ma^n|m \space and \space n \space are \space coprime \}$ using Nerode theorem prove that $L$ is irregular. From Nerode theorem I know that $L$ is regular if and only if the number of ...
user avatar
0 votes
0 answers
20 views

Prerequisite on $L$ so $L^*$ is finite

I need to find a sufficient prerequisite on formal language $L$ over alphabet $\Sigma$ so that $L^*$ is a finite language. I say that language $L^*$ is finite if and only if $L = \{ \varepsilon \}$, ...
user avatar
0 votes
0 answers
23 views

Prove non regularity of the language a^n where n is an even or a prime number, with the pumping lemma

How to prove that the language that is the union of the language where $n$ is an even number and the language where $n$ is a prime number is non-regular with the pumping lemma? I know how to prove ...
user avatar
0 votes
1 answer
39 views

What is a prefix set?

I am trying to understand the following definition of prefix set - "A prefix set is a language $A \subseteq \Sigma^*$" such that no element of A is a prefix of any other element of A. I came ...
user avatar
0 votes
0 answers
26 views

Creation of nondeterministic finite-state machine for a word which doesn't contain a certain symbol

The given alphabet is $$\Sigma = \left\{ a, b, c \right\}$$ I am looking for a nondeterministic finite-state machine which accepts the following words: $$L=\left\{w\in \Sigma^* \mid \exists x\in\Sigma:...
user avatar
0 votes
1 answer
38 views

Automata - Prefix

Assume we have $L=\{ab\}$, then is it correct to say that $\mathbb{prefix}(L)=\{\epsilon,a,b,ab\}$ ? I mean - is epsilon included in every prefix? If I have $L=\{a^*a\}$, then in this case $\mathbb{...
user avatar
  • 654
0 votes
2 answers
51 views

Find a CFG for all the binary strings in which the characters in $i$ and $i + 2$ positions are same, and the length of the string is at least 2.

I have homework which is about CFGs, their simplification, and their normalized forms. I have also seen some examples on the internet, but unfortunately, I could not solve the below question. All the ...
user avatar
0 votes
1 answer
44 views

Writing a grammar that creates a specific language from a given grammar in Chomsky normal form

Given a grammar in Chomsky normal form that creates a language $L$ over alphabet $\Sigma$, that the letter z doesn't belong to $\Sigma$, without the empty string. I need to write a context-free ...
user avatar
1 vote
1 answer
44 views

the power of commuting

There is an interesting paper The power of commuting with finite sets of words. There I have a question about page 6 sentence:"...which is a contradiction because this word has no suffix ...
user avatar
  • 3,578
1 vote
1 answer
40 views

How to create a grammar with a multiplication, to generate $a^ib^jc^k$ with $k=i \cdot j$?

The exercise I found has this language $L=\{a^ib^jc^k: k=i \cdot j\}$ on the alphabet $\Sigma = \{a, b, c\}$, and although it has nothing to do with creation of grammars, I decided to give it a try. ...
user avatar
0 votes
1 answer
33 views

Converting Grammar to Chomsky Normal Form

I have to convert a grammar to Chomsky normal form, the grammar is something like this (not exactly but this is the important bit) V → W W → wWxXyYzZ | vXy | xX X → xYZ | xY | xW | zZ Y → xX | wW | wV ...
user avatar
2 votes
1 answer
35 views

How does the finitely axiomatized formalization of predicate logic correspond to natural deduction for predicate logic?

I'm really interested in using Metamath, but Metamath comes with a funky version of predicate logic. Substitution is not allowed in Metamath, so Metamath employs Tarski's system S2 which is "...
user avatar
0 votes
0 answers
36 views

Using Kleene Star to define set of all tuples?

How is a set $S$ of all the ordered tuples with elements from universe $\mathbb U$ defined? For instance, $S = \{(), (x), (x,y), (x, (x,y))...\} \land x,y \in \mathbb U$. Is the Kleene Star function ...
user avatar
  • 939
0 votes
1 answer
39 views

Finding the equivalent regex for a formal grammar

We have the following formal grammar: $a, b$ are terminal symbols. $S, A, B$ are non-terminal symbols. $S$ is the startsymbol. Thinking in terms of a nondeterministic finite automata $q0$ indicates ...
user avatar
2 votes
1 answer
54 views

CFG for $\{0^i1^j0^k\mid i+2j=3k\}$

Edited: I try to find a Context-Free grammer for $\{0^i1^j0^k\mid i+2j=3k\}$ as follow \begin{align*} S&\to 000S0| 111B00| 01B1| 001B1|\lambda\\ B&\to 111B00| \lambda \end{align*} But ...
user avatar
  • 21
3 votes
1 answer
79 views

What is $\Sigma\cap\Sigma^*$?

Let $\Sigma^*$ be set of all strings over symbols $\Sigma=\{a,b\}$. Adopting the most common definitions what is $\Sigma\cap\Sigma^*$? I'm aware that this question is ambiguous. I just wonder what the ...
user avatar
  • 31
0 votes
1 answer
29 views

How do you show that the language $L= \{ a^nb^nc^na^kb^lc^m \mid l,m,n \geqslant 0 \text{ and } k >0 \}$ is not context-free.

This is somewhat similar to another question I asked here. In that case you could apply the pumping lemma by pumping down on $a^nb^nc^nabc$ . However when $>$ is replaced by $\geq$ for all $\{k,l,m,...
user avatar
  • 1,898
2 votes
2 answers
48 views

Prove or disprove that $(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$ where $L_i$ denotes a formal language

Prove or disprove that $$(L_1\cap L_2)L_3 = L_1L_3\cap L_2L_3,$$ where $L_i$ denotes a formal language Proof: $$\begin{align} (L_1\cap L_2)L_3 &= \{xy \mid (x \in L_1 \land x\in L_2 ) \land y\in ...
user avatar
  • 83
0 votes
1 answer
47 views

proof that L is regular

Given that $A$ is a regular language and $B$ a regular or non-regular language, prove that $L$ is regular: $$L = \{w | wx \in \text{A such that }x \in B\}$$ We can say that L is a subset of A. Regular ...
user avatar
  • 1
0 votes
1 answer
60 views

What exactly is this 'language' for my theory computation course saying?

In the manner of 2 + 2 telling me to add two and two together, what is this trying to say: I'm not asking for an answer (I assume it's some sort of equation), just a starting place. Thanks a million.
user avatar
  • 11
0 votes
0 answers
69 views

What does a language parameterizing another language mean?

I am reviewing my class notes, and I came across this expression - The $n$-th slice of $A \subseteq \Sigma^*$ is $A_n = \{x \in \Sigma^* \mid {\langle n,x \rangle} \in A \}$ $C$ parameterizes $D$ (...
user avatar
0 votes
3 answers
96 views

$a^nb^n$ language vs $a^nb^m$

I always read that $\{a^nb^n \mid n>0\}$ is not a regular language because automata doesn't have memory, while $\{a^nb^m \mid n, m>0\}$ is regular because we don't have to remember anything ...
user avatar
0 votes
1 answer
43 views

Building a DFA from another DFA.

Let the language that the DFA accepts have a different definition. A word is in the language if and only if when we finish reading it we reach an accepting state AND atleast one time passed through ...
user avatar
  • 2,029
0 votes
1 answer
24 views

Solution Verification: Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular.

Prove or Disprove: If $L$ is an irregular language and $F$ is finite language, then $F\cap L^+$ is regular. Note: $L^+=\bigcup_{i=1}^{\infty}L^i$. I will be attempting to prove this statement. ...
user avatar
  • 2,029
1 vote
1 answer
42 views

Regular expression rules for union and concatenation with $\epsilon$ and $\emptyset$

I have four rules here that are true and I wanted to make sure I have a general intuition as of why. These aren't meant to be rigorous proofs, but rather simple explanations. Suppose $R$ is a regular ...
user avatar
  • 37
1 vote
0 answers
37 views

Natural Deduction - Restriction to closed formulas?

Is it typical for formal natural deduction systems to restrict theory axioms and deductions rules to ensure that only closed formulas (formulas with no free variables) appear in proofs? Or is the ...
user avatar
0 votes
0 answers
24 views

Prove the generated language of a grammar. (Why these four cases?)

Question: Let $G_4 = (V_N,V_T,S,F)$, where $V_N = \{S\}, V_T = \{a,b\}$ and F = {S → λ,S → SS,S → aSb,S → bSa}. The generated language is: $L(G_4) = \{P ∈ \{a,b\}^∗ | N_a(P) = N_b(P)\}$, $N_a(P)$ and $...
user avatar
0 votes
1 answer
36 views

What type of Automata can accept just Theorems of Propositional Calculus

As per title: What is the weakest type of automata that is capable of accepting just the theorems (deducible from any specific set of axioms) of Propositional Calculus (i.e. truth functional logic). ...
user avatar
0 votes
1 answer
50 views

Understanding languages for Finite State Automata

Hi I'm learning about finite state automata. I understand what a language is but I don't understand what this syntax is telling me about it. $L = {\{a,b\}}^{*}{\{aa,bb\}}{\{a,b\}}^{*} $ Could you help ...
user avatar
2 votes
1 answer
34 views

How to formally define this language of hereditarily finite sets?

Suppose we have an alphabet of three characters, which are the left brace, the right brace, and the comma. I want to define a language over this alphabet which corresponds to the hereditarily finite ...
user avatar
  • 13.3k
2 votes
0 answers
65 views

What do semi-formal proofs that use objects from different areas mathematics look like when completely formalized?

What do semi-formal proofs that use objects from different areas mathematics look like when completely formalized? For example: Using graphs and planarity to show that circles cannot be used to draw ...
user avatar
  • 51
0 votes
0 answers
45 views

What are the expressions that are formally allowed to write down

Note: I don't have any education whatsoever in logic. This question is supposed to be a mixture of a reference request to sources I can teach myself this sort of knowledge from as well as a question, ...
user avatar
0 votes
0 answers
25 views

Can an empty language be associated with a non-empty alphabet?

As far as I am aware an empty language cannot contain an empty word (string). However, can it be associated with a non-empty alphabet, that simply remains completely unused?
user avatar
0 votes
1 answer
44 views

Cardinality of a language $L_\Sigma$ over a decidable signature $\Sigma$

In the middle of a proof of a theorem I was studying, in order to prove a cardinality argument, there was the following statement: Note that $|L_\Sigma|=|\Sigma|+ \aleph_0$ Where $L_\Sigma$ is a ...
user avatar
11 votes
3 answers
476 views

Is a formal language an algebraic structure?

I am having trouble confirming whether or not a formal language is an abstract structure or algebraic structure. As far as I am aware, a formal language is a set $W$ of well-formed formulae. On ...
user avatar
  • 9,125
0 votes
1 answer
51 views

computation by commuting

I have some doubts about your paper Computing by commuting (abstract is copied below): What do these sentences say (my REMARKS on what I do not follow are numbered by 1,2): " the choice of a word ...
user avatar
  • 3,578
2 votes
1 answer
73 views

How to show that if there's a mapping reduction from L to its complement, it doesn't imply that L∈R?

I have the following prove/disprove claim: if $$L\leq_m L^{c}$$ then $$L\in R$$ I figured out that I can theoretically provide a counter-example where both $$L,L^{c}\not\in(RE\cup co-RE)$$ but ...
user avatar
2 votes
0 answers
56 views

Are there any proof that show something about this language?

Suppose we show any positive rational number with alphabet a string $S$ on $\{0,1,\#\}$ that $S=x_kx_{k-1}\dots x_1\#y_ky_{k-1}\dots y_1$ such that $x_i,y_i\in\{0,1\}$ show an rational number. How it'...
user avatar
  • 21
0 votes
0 answers
37 views

Does a string's "characters" refer to a position in the string, or a value in the alphabet?

This is just a terminology question about the term "character" in the formal theory of strings of symbols. Does the term "character" refer to a particular indexed position in the ...
user avatar
  • 5,401

1
2 3 4 5
38