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

learn more… | top users | synonyms

1
vote
2answers
58 views

Sigma hierarchy of logical formulae

In some papers on mathematical logic I've found references to hierarchy like $\Sigma_1^0$-sentence and so on. What does it mean? What is $\Sigma_n^m$, what is $n$ and $m$ here?
1
vote
3answers
63 views

How does one generally use partial function in logical statements?

How does one generally use partial function in logical statements? How it's done in practice? Specifically, let $M$ by a Turing machine, $f_M:\{0,1\}^*\to\{0,1\}$ the characteristic function which ...
0
votes
0answers
29 views

Help with formulating a mathematical logic formula

I need to write a precise mathematical expression to formulate an algorithm that could be implemented in software. It has the following simple logic: An Internet user of the software in a ...
0
votes
1answer
56 views

Natural definitions of families of subgraphs

Cluster analysis is a vibrant area of applied mathematics, "used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics". A subfield ...
0
votes
1answer
44 views

Z notation - Does operation refinement make an operation more deterministic or even more non-deterministic?

I've stumbled about the following statement: An operation $b$ refines an operation $a$ correctly if and only if $a$ is more deterministic than $b$ As I would guess, it's exactly the other way ...
0
votes
0answers
22 views

Define the set of valid algebraic expressions ALEX as follows:

I am trying to find set of valid algebraic expressions and I know how to do them in math way and my question is how would I be able to do them in syntax rules ? This is the question. ...
2
votes
0answers
64 views

Prove that $\overline{L}$ is not recognizable by showing that $B_{TM} \le_m L$

$\textbf{Problem}:$ $L$ = $\{\langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ such that for some $x \in \{0,1\}^*$, $M$ does not halt on input $x\}$. $B_{TM}$ = $\{ \langle M \rangle$ | ...
0
votes
1answer
25 views

showing language that is non-regular using pumping lemma

I am looking over pumping lemma and the author is using it to show that the language is non-regular. {a^n b^n a^n} = {aba aabbaa aaabbbaaa........} Is there ...
-1
votes
1answer
23 views

transition graph that accepts only Λ and language a*

I am trying to have a transition graph that accepts only Λ and also one that accepts language a* ...is this ok ??? transition graph that accepts only Λ transition graph that accepts language a*
0
votes
0answers
17 views

Build a Transition Graph that accepts the language L…

I need to build a transition graph that accepts the language L of all words that begin and end with the same double letter, either of the forms aa......
0
votes
1answer
27 views

Creating a Push Down Automaton from a Grammar

I have the following grammar, but I'm not sure what exactly it is that it does: $\qquad\begin{align} S &\to S \vee T \mid T \\ T &\to T \wedge F \mid F \\ F &\to p \mid \thicksim p ...
0
votes
1answer
31 views

Which strings does L language produce?

Let $L = 1 \cup (01 \cup 10)(00 \cup 11)^*0$. Which are the strings $L$ produces? I thought the ones that have even number of zeroes and odd number of $1$. But, you can not produce $111$. Then I ...
0
votes
1answer
51 views

Give context-free grammars that generate these languages

Give context-free grammars that generate these languages {a^(2i) b^(3k) c^(4i) | i => 1, k => 1} {a^(i) b^(k) c^(k) a^(i) | i => 1, k => 1} I am seriously stuck here. Esp for the 1st one. For the ...
1
vote
1answer
56 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...
0
votes
1answer
38 views

What does it mean for a Turing machine $M$ to accept $\epsilon$

Suppose $B_{TM}$ = $\{ \langle M \rangle$ | $M$ is a Turing machine over $\{0, 1\}$ and $M$ accepts $\epsilon\}$. I do not understand what it means for $M$ to accept $\epsilon$. Can someone explain ...
0
votes
0answers
12 views

machine accepting words using Transition Graphs

I am preparing for an exam next week, and I am practicing some Transition graphs problems so I would like to know if I am doing this right or not. As you can see here I have machines to see which one ...
3
votes
0answers
90 views

Proving a language is not recognizable

I have the following question that I just want to verify I have done correctly. Let $L$, $L_1$, $L_2$ $\subseteq \Sigma^*$ such that $L = L_1 \cup L_2$, and $L_2$ is decidable. Prove that if $L$ is ...
0
votes
2answers
101 views

Prove the language $\{a^k b^l : k \neq l \}$ is not regular

Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ...
4
votes
1answer
55 views

Proving that a language is not context-free

Given the language $$L = \{ a^p \mid p\, \text{IS NOT prime} \}$$ is $L$ Context free? If not, prove that it's not. May I have some suggestions on how to use the pumping lemma to prove this, ...
1
vote
1answer
45 views

Generalising cover maps from monoids to semigroups

Let $T,S$ be monoids. A partial surjective mapping $\psi : T \to S$ is called a cover map if for each $s \in S$ there exists some $\hat{s} \in T$ called a cover of $s$ such that for each $t \in ...
1
vote
1answer
39 views

Question about equlaity of two language, simple but tricky.

I found the following question tricky: If $A$ is a language, when will $A^*=A^+$? By definition, $$A^* = \bigcup^{\infty}_{i=0}A^i = A^0 \cup A^1 \cup A^2 \cup \cdots$$ $$A^+ = ...
1
vote
2answers
19 views

A question about operations on languages.

I come across this problem on a book. It states that: for languages A and B, $(A\cup B)^* = (A^*B^*)^*$. I know that the definition of star closure is $\left(\bigcup^{\infty}_{i=1}\right)A^i$. But so ...
2
votes
1answer
33 views

A correct proof for this pumping lemma example?

Given the language $L = \{0^{2^n} | n \geq 1\}$ So, the language contains all strings that have $2^n$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
5
votes
1answer
151 views

Proving that e.g. 421 is prime in a formal system

I'm working in the formal system Metamath, and in the course of learning about number theory I've become acquainted with theorems, such as Bertrand's postulate, that require hand-calculation that a ...
1
vote
2answers
59 views

The halting problem for tapes that are or are not completely blank

Is it possible to construct a Turing machine that halts only if the tape is not completely blank? Also, is it possible to construct one to halt if the tape is completely blank? Intuitively, I think ...
1
vote
1answer
68 views

If $L_1 \cap L_2$ is decidable, prove/disprove that $L_1$ and/or $L_2$ are decidable

Question: Let $L_1$ and $L_2$ be languages over the alphabet $\Sigma$. If $L_1 \cap L_2$ is decidable, then $L_1$ is decidable or $L_2$ is decidable (or they both are). Definition of a decidable ...
1
vote
2answers
74 views

If the Kleene star of countable sets is countable, how are the real numbers uncountable?

The formal languages we use to represent number systems are interchangeable, which is why we don't hesitate to use different notations, e.g. hexadecimal, octal, binary, etc... to represent the reals. ...
1
vote
1answer
29 views

Pumping Lemma Squares Proof Explanation

I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ...
0
votes
1answer
41 views

Expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$

For any language A, let $A^R$ be $\{x^R \mid x \in A\}$. Then, for arbitrary languages $A$ and $B$, explicitly write down the expressions for $(AB)^R$, $(A \cap B)^R$, $(A \cup B)^R$. I am not really ...
0
votes
2answers
208 views

Regular expression and DFA/NFA questions

If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ...
0
votes
2answers
35 views

Finding the wrong regular expression

Which one of the following regular expressions does not define the language of all strings that ends with a. $(a + b)^*a$ $b^*aa^*(bb^*aa^*)^*$ $[a(ba)^* + b(ab)^*](a + b)^*a$ $(b + aa^*b)^*a(a + ...
3
votes
1answer
40 views

Proof of a Known Claim About Languages

I would like to know how to prove that there is no non-trivial language $L$ that satisfies the following condition: $${\large \left(\overline{L}\right)^* = \overline{L^*}}$$ "Non-trivial" is ...
1
vote
1answer
48 views

Properties of Natural Numbers and Mathematical Induction

When working with natural numbers how to check that the property we consider is "permissible" to speak about? And not like the property "The smallest positive integer not definable in under eleven ...
2
votes
1answer
48 views

Are languages regular if their concatenation is regular?

Let $A, B \subset \Sigma^*$ be languages. If the concatenation product $AB$ is regular, are $A$ and $B$ necessarily regular? I'm inclined to think this is true since the regular language $AB$ has a ...
1
vote
1answer
38 views

Difficulty finding context free grammar for this language

I'm learning context free grammars from languages. Language ${L=\{{a}^{2i}\,{b}^j\,{c}^k\,|\,3i=j+k, i \gt 0\}}$ My guess is $${S\rightarrow BA}$$ ...
2
votes
1answer
38 views

Context free grammar for language

I'm learning how to generate context-free grammar for a language. $L=\{{a}^i {b}^j {c}^k\, |\,i=j\lor j=k$ Here is how I tried ...
0
votes
3answers
20 views

If $s \geq 3$, $3$ divides $s$, and $t = s/3$, then $t+1 < s$.

I am using the pumping lemma to prove a language is not regular, and would like to assert what I have stated in the title of the question to complete my proof. That is, if $s \geq 3$, $3$ divides $s$, ...
2
votes
1answer
51 views

Prove that RE is closed under reduction

Prove that the class RE is closed under reduction. Definitions: A language $ A \subseteq \Sigma^*$ is called reducible to $ B \subseteq \Gamma^*$ ( denoted by $A \leq B$) if there is a computable ...
1
vote
2answers
78 views

Prove context-free or not context-free

Given the following language: $L=\{a^{p^2}|$ $p$ is prime$\}$ How can I show that this language is not context free using the pumping lemma? I'm having trouble breaking it up to $s = uvxyz$. would ...
1
vote
1answer
31 views

Stronger condition then ultrametric condition on metric space

A metric space $(X,d)$ is called an ultrametric space if it is a metric space and fulfills the stronger triangle inequality (see Wikipedia) $$ d(x,y) \le \max\{ d(x,z), d(z, y) \}. $$ Examples are ...
1
vote
1answer
47 views

Finding Nerode equivalence classes

How am I supposed to find the equivalence classes of a Language? What should I think? For instance, having a language $$L =\{a^n b^m \mid n,m \ge 0, (m+n) \bmod2=0)\}$$ I can have: $[a^n]$ with ...
2
votes
2answers
170 views

Can We Represent Every Real Number Using Only Finite Memory?

This question arises from a comment I recently read in another question. My question is whether we can represent every real number using only finite memory. I will clarify what I mean by represent ...
1
vote
1answer
63 views

Push down automata for context free grammar

I'm having trouble finding the PDA for this language $L = \{x^{3i} y^j z^k\ |\ i \ge 0 \land k \gt 2j \gt 0\}$ The ...
0
votes
0answers
27 views

how to generate the numbers nontrivially stable under the permutions of their primes?

every natural number $>1$ has a unique expression entirely in terms of the primes $2,3,5,\dots$ in obtaining this, note that the usual factorization is only step 1 of a possibly length process. ...
1
vote
1answer
55 views

Closure properties!

If $L_{1}$ is a context-free language and $L_{2}$ a regular one,use the closure properties and explain if the language $L_{2}-L_{1}$ is also context-free or not.How can I do this?
1
vote
0answers
41 views

Language requiring a DFA with a certain number of states to implement

For any function $f\colon\{0,1\}^n\to\{0,1\}$, define a language $S_f = \{(b_1,b_2,\ldots ,b_n)\in\{0,1\}^n : f(b_1,b_2,\ldots ,b_n) = 1\}$. So all words in the langugage has same length $n$. I have ...
1
vote
1answer
40 views

(Transformation) Semigroups, the semigroup $\mathbf D_n$ and the wreath product

I have some trouble understanding the following proof, were I can't even figure out how some terms are defined. But first I state some definitions and preliminary lemmas. A transformation semigroup ...
0
votes
1answer
20 views

composition of uniform substitutions

Let A be a nonempty alphabet. In a previous question, I asked for the definition of a uniform substitution. Now, my question is this. Is the composition of two substitutions itself a substitution? I ...
11
votes
1answer
306 views

What underlies formal logic (or math, generally)?

I read a useful definition of the word understanding. I can't recall it verbatim, but the notion was that understanding is 'data compression': understanding happens when we learn one thing that ...
1
vote
3answers
46 views

Formal definition of string-to-term substitution

Forgive me if this question seems elementary. Let L be a nonempty alphabet. We have an intuitive notion of substituting words for letters in a word. For example, substituting 'cd' for 'b' in the word ...