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
1answer
8 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
13 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
69 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
69 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
23 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 ...
-2
votes
2answers
37 views

Why is a the right answer? [closed]

[ I dont understand Why a is the answer? Why is c NOT?
0
votes
2answers
19 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
16 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
61 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
19 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
48 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
23 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
27 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
59 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
39 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
35 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
74 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
27 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
48 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
30 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
51 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
29 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
48 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
41 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
39 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
46 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
60 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
21 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
93 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
55 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
18 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
33 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
36 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
14 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
37 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
113 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
16 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 ...
0
votes
1answer
15 views

Do the initial segments of the strings of a regular language form a regular language?

Let's say you have a set of strings $R$. A string $s$ is part of my language $S$ iff there is a string $r \in R$ such that $s$ is an initial segment of $r$ (you can get $s$ by removing characters from ...
1
vote
0answers
19 views

Chomsky Normal Form Transformation

I've been struggling a bit with creating the Chomsky normal form derivation of a grammar that I have been given The grammar in question is: $S \to BB \mid 0A0 \mid 1B1 \\ A \to C \\ B \to S \mid ...
0
votes
1answer
50 views

How to prove whether a language is decidable and/or semi-decidable (or neither) using reduction?

I think I understand the basics of reduction, however I'm far from confident with using the techniques. I have a couple of examples that I'm struggling with: L1 = {< M > | M accepts an infinite ...
0
votes
1answer
98 views

What does arbitrary number mean?

A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary number of digits). Is it true ? My attempt : Arbitrary length means variable length, and there ...
0
votes
1answer
23 views

Identify the class of language?

Given a set $$S=\{x∣ \text{there is an x-block of 5's in the decimal expansion of π}\}$$ (Note: x-block is a maximal block of x successive 5's). Identify class of language? Somewhere it ...
1
vote
0answers
49 views

Is $r(^∗)=r^∗$ valid regular expression?

Which of the following regular expression identities is/are TRUE? $r(^∗)=r^∗$ $(r^∗s^∗)=(r+s)^∗$ $(r+s)^∗=r^∗+s^∗$ $ r^∗s^∗=r^∗+s^∗$ My attempt : I can't say anything, but it should be ...
0
votes
1answer
58 views

Read-only Turing machine recognizes only regular languages?

Show that the Turing machines, which have a read only input tape and constant size work tape, recognize precisely the class of regular languages. According to wiki : A read-only Turing machine or ...
1
vote
1answer
24 views

Checking if Post Correspondence Problem has a Solution

I have the following problem I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?
0
votes
1answer
25 views

For a regular language $L$, $Z(L)=\{x \in \Sigma ^* | \exists w \in \Sigma^*, xww\in L \}$, Is $Z(L)$ regular?

I was able to prove it is regular by induction on the length of the regular expression of $L$. I was wondering if there is a better way to prove it. Better in the way that it is not "Induction ...
1
vote
1answer
14 views

How to prove that $(a∪b)^*⊆b^*(ab^*)^*$? (formal languages)

(a and b are two formal languages). I tried to prove that using the fact that for languages $L_1, L_2$ we get: $(L_1∪L_2)^* =(L_1^* L_2^* )^*$ , but I got stuck here: $(a∪b)^* = (a^* b^* )^*⊆b^* (a^* ...