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
3answers
48 views

Proving two languages are equal

Q: Show that $\{a,b\}^* = \{a\}^*(\{b\}\{a\}^*)^*$. I am aware of the fact that both sides are sets, infinite sets actually. So for example showing that both sides are subsets of each other would ...
2
votes
2answers
40 views

How to check whether arbitrary finite [syntactic] monoid is aperiodic or not?

Does there exist an algorithm to decide whether a (finite in my case) syntactic monoid is aperiodic or not? By definition, a monoid is aperiodic if for each $x$ from monoid there exists an $n$ with ...
0
votes
1answer
49 views

Prove concatenation of strings is associative

Q: Prove, using the definition of concatenation given in the text, that concatenation of strings is associative. DEFINITION: The concatenation of strings $x$ and $y$, written $x \circ y$, ...
1
vote
1answer
24 views

How can I interpret a multiply-quantified statement?

∃ x ∈ R such that ∀ y ∈ R, x + y = 0. Can anyone help me rewrite this statement in plain english without symbols or variables? So far I have "There exists a real number whose number and other number ...
0
votes
2answers
18 views

What is the automaton recognising the language generated by G?

Why is B not accepted as an answer?: S --> 0A A --> 0A A --> 1B B --> 1B B --> e Which ends up in the state of the automata is in the accept state.
1
vote
1answer
18 views

What is the Right Context of a Word in Formal Langauge Theory?

I am reading this paper and am unable to understand this notation in section 2.2 - The right context of a word $u$ according to a language $W$ is the language {$u^{-1}w$ | $w \in W$}. The ...
0
votes
2answers
32 views

Is there a language like L in which $\overline {L^*} = \overline L^*$?

Assume that for every language L over the alphabet $\Sigma$, we define $L^*$ , $\overline L$ , $\Sigma^*$ & $L^n$ like this : $L^n$ means joining L to itself n times. For an alphabet like ...
0
votes
1answer
87 views

Stronger Pumping Lemma for Context Free Languages

Hi Math Stack Exchange, Taking a class in automata theory, and having real trouble proving the following strong automata theorem for context free languages (from Sipser, Problem 2.37): If L is a ...
1
vote
1answer
25 views

How to identify context free language?

Consider the following context-free grammars$:$ $G_1: S → aS|B, B → b|bB$ $G_2: S → aA|bB, A → aA|B|ε, B → bB|ε$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$, ...
0
votes
1answer
31 views

Identify language of given PDA?

Consider the transition diagram of a PDA given below with input alphabet $Σ =\{a,b\}$ and stack alphabet $Γ = \{X,Z\}. Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA. ...
0
votes
1answer
41 views

Reduction to/from REC and RE language?

Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to ...
1
vote
1answer
31 views

Subtracting a context-free language from a regular language

I have the language $L=\{a, bb\}^*-\{a^ib^i|i\geq1\}$ and I have to show that $L$ is context-free. The first language is Regular, if I'm not mistaken, and the second is a well known context-free ...
1
vote
1answer
21 views

confusion of an example for Powerset construction

I have an example of Powerset construction from the lecture. Powerset construction is applied on automata A1. The result is automata A2. You could see I do Powerset construction myself below the ...
0
votes
1answer
86 views

Is the set of languages over an alphabet Σ missing k words from Σ* countable?

My original question is whether $\mathscr{L}$, the set of all languages over an alphabet $Σ$, each of which missing finitely number of words from $Σ$* is countable. I think I can prove the set is ...
1
vote
2answers
72 views

What is so special about categories that lead people to use them to “formalize math”?

There are countless interesting structures - lists, trees, maps, graphs. Yet, categories - which, if I understand, is just a graph with some constraints on its shape - are apparently special somehow, ...
0
votes
0answers
30 views

Queue automaton algorithm for accepting primes

What is an example of a queue automaton algorithm that accepts prime numbers, encoded as strings of prime length? For example, if the input is either of ...
0
votes
2answers
23 views

Reverse of binary number

Let us say that x is a set of binary numbers $$x = \{0, 1, 1001\}$$ Am I correct that $x^R$ is equal $$x^R = \{0,1,1001\}$$ or is it: $$x^R = \{1,0,0110\}$$ What I mean by that is: do we create a ...
1
vote
1answer
19 views

Definition of generators in the context of groups as languages

In the book "Word processing in groups" by Epstein et al. (p.28-29), the definition of generators begins with the following sentence: Let $G$ be a group, $A$ an alphabet and $p \colon A ...
0
votes
2answers
81 views

Is it possible to have logic without syntax (with only semantic proof methods)?

In one paper I have read a note "Thus, unlike approaches which make use of full first order logic, unprovability of a formulae with respect to a agent specification can be shown by each of two ...
1
vote
1answer
30 views

Emptiness and infiniteness decidable for recursive languages?

The problem of determining whether a recursively enumerable language is empty or infinite cannot be solved. The proof goes by reduction to the problem of decidability, which is known to be unfeasible ...
3
votes
1answer
71 views

How many DFA's exist with two states over the input alphabet $\{0,1\}$?

How many DFA's exist with two states over the input alphabet $\{0,1\}$? My attempt : Input set is given. So, we have 3 parts of DFA which we can change: Start state Transition Function Final ...
0
votes
1answer
24 views

How to define that in which hierarchy certain language belongs?

Chomsky hierarchy has four types of languages and grammars. If we have some language $L$, what are the tools for finding out the correct family of languages it belongs? I know that there are pumping ...
0
votes
1answer
43 views

Is epsilon a useless symbol and when epsilon does belong into CFL?

Let's say that we have a grammar with multiple productions. And there is production from B to epsilon. Is B a useless symbol? If there is another production, let's say B to aB. Now B is useless, ...
3
votes
1answer
102 views

The Mathematics of Finite State Automata

I am a final year undergraduate mathematics student preparing to undertake my BSc-HONS project, provisionally titled for the time being, "Finite State Automata and Regular Languages". Having had a ...
0
votes
1answer
44 views

How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Could you explain me, how can I check, that the language of first context-free grammar (G1) is a subset of the language of second context-free grammar (G2). G1 and G2 are two LL(1) grammars with ...
0
votes
0answers
41 views

Regular and context free language

Let $A$ be a set represented by a regular expression $0^*1^*$ and let $B=\{0^n1^n\mid n\geq 0\}$. It is known that $A$ is a regular language, while $B$ is a context-free language. I understand that ...
2
votes
2answers
82 views

formal languages - why is this regular?

I'm studying for a test on formal languages and automata. I came upon the following question (translating, so i apologize for the non-formal english): $L_1$ is the language composed of all words ...
1
vote
1answer
30 views

Using Pumping Lemma to prove that $L=\{a^mb^{3m}:m\in\mathbb{N}\}$ is not recognizable over $A=\{a,b\}$

[Pumping Lemma]: Let $\mathcal{A}=(Q,A,\cdot,i,T)$ be a (complete and deterministic) automaton and let $L=L(\mathcal{A})$ be the language recognized by $\mathcal{A}$. If $L$ is infinite and ...
0
votes
1answer
49 views

Is $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ a context free language?

I need some help in finding and proving (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{j}o^{j}1^{k}o^{k}1^{i} | i,j,k>0\}$ is a context free language. thanks!
1
vote
1answer
38 views

Is $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ a context free language?

I need to find and to prove (by the pumping lemma or by building a grammar) if $L=\{o^{i}1^{i}o^{j}1^{i} | i,j>0\}$ is a context free language. I would like to get some help. thanks!
1
vote
1answer
61 views

Language with middle third removed

Originating from Sipser's book: Let $A$ be any language, define $A_{{1\over3}-{1\over3}}$ be the subset of strings of $A$ whose middle third is removed. The solution I came across makes the ...
0
votes
1answer
25 views

Using induction for an easy proof for formal languages

I am having trouble to understand the way of using a induction for the following example: Let $\Sigma \overset{\Delta} = \{a, b\}$ and $S_1 \overset{\Delta} = \{a^n \mid n \in \Bbb N\}$. Prove ...
-1
votes
1answer
55 views

Using induction to prove a description of a formal language [duplicate]

One of my tasks is to proof that something is correct or incorrect using induction. Since I am from Germany and don't know the right word in English I do my best to give all necessary info. We are ...
0
votes
1answer
30 views

Prove that theory is not Henkin one

The definition as it was given to me: The theory $T$ is Henkin theory, if and only if for every formula $\phi$ in $T$ we have constant $c$ language of $T$ such as $T \vdash \exists x \phi \to ...
0
votes
1answer
94 views

Is there a subtle difference between NOEXTEND(A) vs NOPREFIX(A)?

My question originates from Sipser's book. Let A be a language with the DFA $(Q, \Sigma, \delta, q_{0}, F)$ and define: NOPREFIX(A) = {w $\in$ A| no proper prefix of w is a member of A} NOEXTEND(A) ...
1
vote
1answer
60 views

Prove that two arithmetic grammars generate the same language

In my university's automata theory book it is claimed that the following two arithmetic grammars generate the same arithmetic language but no proof is shown. $G_1=(\{E\}, \{a,+,*,(,)\}, \{E\to ...
1
vote
1answer
41 views

Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

My university's automata theory book claims that the following claim can be proved by induction but it doesn't bother showing the proof. I've tried to prove it myself but I got stuck at the ...
1
vote
1answer
50 views

Representing a $\sigma$ - structure using a signature-$\sigma$ in Mathematical Logic.

In mathematical logic, I have a question regarding how a signature-$\sigma$ relates to a corresponding $\sigma$ structure which interprets the signature-$\sigma$ In Chiswell and Hodges book ...
1
vote
0answers
61 views

A polytime language with no subsets of lesser time complexity

For any integer $l>0$ does there always exist a language with time complexity of order $O(n^l)$ such that it has no subsets of a lesser time complexity ie $O(n^m)$ for any $m< l$. We talk of ...
1
vote
1answer
23 views

Analysing a context-free grammar

Let: $$S \to AC \mid BC\\ A \to aAb \mid aA \mid a\\ B \to aBb \mid Bb \mid b\\ C \to Cc \mid c$$ I need to find if: the word $aabbbcc $ is in the grammar, and if so to write a very left series, ...
1
vote
1answer
95 views

A function given a string ( a program) accepts it if the next program which halts does so in an odd number of steps… is it turing computable

A function which given a string returns 1 if the next program halts with an odd number of steps and 0 otherwise. Is this function computable f(s)=1 if w halts in odd number of steps where w>s and ...
1
vote
1answer
59 views

Semantic values of $\mathcal{L}$-formula in first order Logic?

If $\mathcal{L} = \{P, R, f, g, c_0, c_1\}$, where $P$ is a unary predicate, $R$ is a binary predicate, and $f$ and $g$ are binary function symbols. Let $\mathcal{M} = (D, \mathcal{I})$ be an ...
0
votes
1answer
22 views

Logic formalization for Perfect Graph Matching problem

A matching $M$ in a undirected graph $G(V,E)$ is a subset of the edges of $E$ such that no two edges in $M$ are incident to a common vertex. A perfect matching ${M}'$ is one in which every vertex is ...
0
votes
0answers
42 views

Do we use Z specification language these days?

I am studying organization and properties of CAM (Content Addressable Memory) of a network switch. While searching for applications of Z, I found that there are several formalization projects ...
1
vote
1answer
16 views

There are substrings that are never cut by a smallest grammar.

Define a substring of a string $s$ to be compressible if $|E| = 2$ and the number of non-overlapping occurences $\#_s E$ of $E$ in $s$ is $\geq 3$, or $|E|\gt 2$ and $\#_s E \geq 2$. E.g. $s = a^6 ...
1
vote
2answers
38 views

Is $L_1 = \{w ∈ {0,1}∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$ regular?

Let $L_1 = \{w ∈ \{0,1\}^∗ | \text{w has at least as many occurrences of (110)’s as (011)’s}\}$. Let $L_2=\{w ∈ \{0,1\}^∗ | \text{ w has at least as many ...
0
votes
0answers
15 views

Levenshtein distance approach to smallest grammars.

Let $G$ be a smallest grammar for a string $s$. Consider the operations: $\text{app}(k,c)=$ append a terminal $c$ to rule $k$. $\text{exp}(k, j)=$ expand recursively rule $j$ and append to $k$ ...
0
votes
2answers
39 views

Is constructing a DFA enough to prove that a language is decidable?

If the axiom $A_{DFA}$ is known to be decidable, would simply constructing a $DFA$ diagram be enough to prove that $L(M)$ is decidable? Most of what I can find on the internet tells me that you need ...
3
votes
1answer
122 views

Stuck on GEB chapter 9 - is b a MU number? is b a TNT number?

I'm reading through Gödel, Escher, Bach, and I found myself stuck at chapter 9. I've been rereading through several times already, but I must be missing something. To clarify my background, I'm a ...
0
votes
1answer
25 views

when do we say a grammar to be unambiguous with respect to parse tree and derivation tree?

In normal terminology we say that both the parse and derivation trees are same in meaning so if a grammar derives one string with left derivation as well as right derivation then it is ambiguous , if ...