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

12
votes
3answers
276 views

Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in do not ...
1
vote
1answer
33 views

How to prove $\forall x,y\in\mathbb{R} : x^3+x^2y=y^2+xy \Leftrightarrow y=x^2\lor y=-x?$

Let $x,y\in\mathbb{R}$ Assume $x^3+x^2y=y^2+xy$ Then $x^2(x+y)=y(x+y)$ Then either $(x+y)=0$ or $(x+y)\ne0$ Assume $x+y=0$ Then $y=-x$ Assume $(x+y)\ne0$ Then $y=x^2$ Then $x^3+x^2y=y^2+xy ...
4
votes
1answer
32 views

Identify recursive languages?

Consider the following languages. $L_1 = \{<M> \mid M \text{ takes at least 2016 steps on some input}\}$, $L_2 = \{<M> \mid M \text{ takes at least 2016 steps on all inputs}\}$ and ...
1
vote
2answers
73 views

Help with finding the generating function of this language?

I've simplified this a bit so that I can just get help with the basic steps. Say we have a language of all words over $\{a,b,c,d\}$ where the only letters allowed to commute are $ab$. I need help ...
0
votes
1answer
18 views

What is flaw on my proof to identify any string of $L_2$ using single stack?

Consider the following languages: $L_1=\{a^nb^mc^{n+m}:m,n≥1\}$ $L_2=\{a^nb^nc^{2n}:n≥1\}$ Which one of the following is TRUE? Both $L_1$ and $L_2$ are context-free. $L_1$ is context-free while ...
0
votes
2answers
42 views

Formal languages

Let language $L$ be denoted by the regular expression $a^*b^*$ What is wrong with the following “proof” that $L$ is not regular? Assume that $L$ is regular. Then it must be defined by a DFA with k ...
0
votes
2answers
33 views

formal languages and computability concepts

Prove whether or not language $L$ ={$a^pb^q : p ≥ 100$ and $q ≥ 100$ are fixed integer values, and $i ≥ 0$} is regular. I'm not sure how to prove this.
0
votes
1answer
34 views

Formal languages and Computability

Can someone please tell me how would you start proving this? Thanks Prove whether or not language L = {a^(p+qi) : p and q are fixed integer values, and i ≥ 0} is regular.
0
votes
1answer
22 views

Strong induction on formal language proof

Q: Show that $\sum^* = L_1\sum^*L_2$ if $e\in L_1 \subseteq \sum^*$ and $e\in L_2 \subseteq \sum^*$ for any alphabet $\sum$. In these equivalence proofs, one way is usually easy. I guess it ...
1
vote
3answers
51 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
59 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
20 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
34 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
94 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
39 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
47 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
37 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
24 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
88 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
74 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
32 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
25 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
35 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
78 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
25 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
50 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
83 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
99 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
51 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
24 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
96 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 ...