Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
7 views

Is there always a reduction function between two languages in R? [on hold]

I believe this sentence to be true, but i could not manage to prove it.
0
votes
0answers
12 views

Use proven constructions to derive a DFSA.

$$ M1 = < \{A,B,C\}, \{a\}, \{(A, a)\} \to B, (A, a) \to C\}, A, \{B\} >$$ Assume that $T(M1) = {a}$. Use proven constructions to derive a DFSA, $M2$, from $M1$ such that $T(M2) = T(M1)$. My ...
1
vote
1answer
17 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language

How would you design a context-free grammar for the following language? $$ L = \{a^{(n^3+1)}\mid n \geq 1\} $$ And derive a Pushdown Automaton that accepts the same language. Any help given would be ...
-1
votes
0answers
19 views

Would it make sense to make a dichotomic tree of all semantic concepts know to humans? [closed]

Being there no semiotics in stackexchange I ask here but I'm no mathematician so be clement on my poor brain when you're about to use vocabulary I didn't know existed :D So I'm asking if there is a ...
1
vote
1answer
39 views

Finding languages such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R [duplicate]

I am struggling to find such languages $L_1$, $L_2$, and $L_3$ such that $L_1\subset L_2\subset L_3$ where $L_1,L_3\notin$ RE and $L_2\in$ R. I know they exist, I need help finding them.
0
votes
1answer
54 views

Finding languages such that $L_{1} \subseteq L_{2} \subseteq L_{3}$ where $L_{1}, L_{3} \notin \mathbb{R}$, $L_{2} \in \mathbb{R}$

I am struggling to find such languages $L_{1}$, $L_{2}$, and $L_{3}$ such that $$ L_{1} \subseteq L_{2} \subseteq L_{3} $$ where $L_{1}, L_{3} \notin \mathbb{R}$ and $L_{2} \in \mathbb{R}$. I know ...
0
votes
1answer
19 views

How many strings are in a A^4 if there is an empty string in the set of strings?

Ive been struggling to answer this question. The question is we have A = {[a],[b],[c]} and I want to know how many strings are in A^4 ( A to the power of 4). And also if one of the strings in A was ...
0
votes
0answers
21 views

number of words in language $L \subset \Sigma$

I had my lecture today about decidable languages and as I am reviewing the material I have from the university, I got quite confused about the following definition: $\emptyset$ doesn't contain any ...
1
vote
0answers
32 views

What are the most efficient date systems with temporal symmetry?

Most date or time systems have an Epoch, or privileged "starting" point. For example, the Epoch of the Gregorian calendar is 1 A.D. The Epoch of Unix time January 1, 1970. These Epochs introduce a ...
1
vote
0answers
29 views

How to prove that models of indirect and direct RAM machines are equivalent?

as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
3
votes
2answers
50 views

Bijection between $\{0,1\}^*$ and the natural numbers.

So the tasks is to show that $\{0,1\}^*$ is countable. So the idea that i am having is that each number can be mapped to it's own in decimal. $f(1001)= 9$ $f(101)=5$ But what happens with all the ...
1
vote
1answer
69 views

What are expressions in mathematics?

Like algebraic expressions are logarithmic, Experimental, trigonometric, differential, etc., expressions also there? I am not referring to functions, but just expressions or equations. Are their ...
1
vote
1answer
29 views

Language contex-free

$$L=\{a^kb^nc^md^t\mid n+m=2(k+t)\}.$$ So I am trying to figure out if this language is CFL. So trying to prove that it is not CFL with the pumping lemma, I am not getting anywhere (using the word $a^...
0
votes
1answer
25 views

Is $L_4$ a CFL?

Consider the following language: $$L_4 = \{a^ib^jc^kd^l : i,j,k,l \ge0 \wedge i=1 \Rightarrow j=k=l\}.$$ Prove or disprove: $L_4$ is a context-free language. To me, it looks like $L_4$ can be ...
0
votes
1answer
39 views

Prove that the grammar defines language

Given grammar G, I have to prove it defines the language of all words which are not palindromes. In other words, $w\in L(G) \Leftrightarrow w\in L $ where $L =$ {w$\in$ $\sum^*$ | w is not palindrom} ...
0
votes
1answer
29 views

Language contex-free or not?

I was wondering whether this language is context-free or not? It's $L = \{ AB ~|~ |A| = |B| \text{ and } A \neq B \}$ . The alphabet is $\{ a, b \}$. In my textbook it's written that it is ...
1
vote
1answer
32 views

how to prove that L is not context free

Given $\sum_2$ = {$\begin{bmatrix} 0 \\ 0 \end{bmatrix}$, $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 0 \end{bmatrix}$,$\begin{bmatrix} 1 \\ 1\end{bmatrix}$} , and a language $L$ = {$...
0
votes
1answer
23 views

What would be the complement of $L =\{a^{n}b^{m}a^{n}b^{m} | n,m \geq 1\}$

I understand the complement of L would be all the strings not in L, but I'm having a hard time writing down the structure of all the strings not in L.
1
vote
1answer
40 views

How to define a grammar which creates a language from words of another grammar without one of the letters?

Let $G=(V,T,P,S)$ be a context-free grammar without $\epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of ...
1
vote
0answers
33 views

How to guess the end of pushdown automata by emptying the stack?

Let language $L=\{\sigma_1w_1c\sigma_2w_2c...\sigma_nw_nc\}$ where: $$ 1\le n\\ \sigma_i\in \{a,b\}\\ w_i\in \{a,b\}^+\\ \exists i:i\le|w_i| $$ and at least one condition from the two conditions ...
0
votes
1answer
11 views

Is there a prefix-free language that can encode any other prefix-free language with at most a constant overheard?

Let $U$ and $P$ be prefix-free languages with alphabet $\{0,1\}$. We say that $U$ can encode $P$ with at most a constant overhead if there exists an injective function $c:P \to U$ and a constant $a$ ...
6
votes
1answer
59 views

For what $n$ is $W_n$ finite?

Suppose, $W_n$ is the set of all words formed by letters '$a$' and '$b$', that do not contain $n$ same consecutive nonempty subwords (that means that for any nonempty word $u$, the word $u^n$ is not a ...
0
votes
0answers
39 views

What do sentences in the theory of the structure $A=(Q,<,n)_{n \in N}$ look like?

I'm working on a problem from Kees Doets, and he mentions the following structures: $X=(Q,<,n)_{n \in N}$ $Y=(Q,<,\frac{-1}{n+1})_{n \in N}$ $Z=(Q,<,q_n)_{n \in N}$ where $\{q_n\}_{n \in ...
2
votes
1answer
27 views

Find the number of words recursively such that there is no palindromic suffix

Given a set of distinct characters $\{a_1, a_2, \cdots , a_S\}$ and a number $N$, find the number of words of length $N$ that can be formed using these letters (repetition allowed) such that there is ...
0
votes
1answer
42 views

Is $L = \{a^{i+j}b^{j+k}c^{i+k} | i,j,k > 0\}$ context free?

This is not an assignment question. Professor gave this for us to think about. I want to say its not context free since in the case $i=j=k$ then we have the language $a^nb^nc^n$ which we know is not a ...
0
votes
1answer
18 views

On left recursive context-free grammars

Definition Context-free grammar $G$ is said to be left-recursive, if there exists such non-terminal symbol $A$, that one can derive from it a word $A\alpha$, where $\alpha$ is a word over unified ...
0
votes
0answers
12 views

If a language is NOT partially decidable, is the complement not partially decidable?

I am trying to figure out if L is partially decidable or not partially decidable. Let L be {encode(x): x is a Turing machine that halts on input encode(x)}.
1
vote
1answer
26 views

Complete Lattice and Concept Lattice

I am taking an online course of Introduction to Formal Concept Analysis and I'm trying to understand The Basic Theorem. Well, if $\mathscr{L}$ is a complete lattice, so $\mathscr{L}\cong \underline{\...
4
votes
1answer
166 views

How many Nerode equivalence classes does the language $x\neq y$ have?

I have a language $L_k$ over the alphabet $\Sigma=\{0,1,\#\}$ defined as follows: \begin{equation} L_k=\{x\#y|x\in\{0,1\}^k,y\in \{0,1\}^*\wedge x\neq y\} \end{equation} I would like to find all the ...
0
votes
1answer
55 views

Given a regular language L, prove or disprove L' is regular

Given $NFA$ $N$ , $L(N)$ regular language and two words $w1$,$w2$ $\in$ $\sum^*$ such that $w1$ $\neq$ $w2$. I have to prove or disprove that $L'=$ {$z\in \sum^*|\exists$ $w1,w2$ :$w1z$ $\in$ $L(N)$ ...
0
votes
1answer
20 views

Identify the Nature of the given Language

If I am true then following two languages are not equal:- $L_1 = \{(a^nb^m)^l / n,m,l \geq 1 \}$ $L_2 = \{(a^*b^*)^*\}$ And I think $L_1$ is not $CFL$, because suppose a case where I put $n=2$, $m =...
1
vote
0answers
97 views

Prove that Dyck language is subset of grammar

last two days I am trying to prove, that Dyck language $L$ over the alphabet $\{[, ]\}$ is a subset of the language $L(G)$ generated by the grammar with rules $\{S \rightarrow [S]S | \epsilon \}$. ...
0
votes
1answer
18 views

Especific terms at Formal Concept Analysis - Translate to Portuguese

I am taking a course of Introduction to Formal Concept Analysis and, as this is my first time with this topic, I could not translate very well some especific terms to portuguese. I hope someone could ...
0
votes
1answer
36 views

Infimum and Supremum (of sets) - Formal Concept Analysis

I am taking a course of Introduction to Formal Concept Analysis and I have an uncertainty about the definition of supremum (least comum superconcept) and infimum (greatest comum subconcept) of formal ...
0
votes
0answers
27 views

build a pushdown automaton that recognizes the reverse language of a given pushdown automaton?

I think it's similiar to NFAs. I replace the finite states of the given automaton for start-states for my new automaton. I do it with $\epsilon$-transition from the start state to the actual finite ...
0
votes
0answers
292 views

Automata theory - How many Nerode equivalent classes for language $L_k$ [duplicate]

Given a constant $k$ we will define the language: $$L_k =\{x\#y \mid x \in \{0,1\}^k, y \in \{0,1\}^* \text{ and } x \not=y\}$$ How many Nerode equivalent class does $L_k$ have? I need to show ...
1
vote
2answers
42 views

Does the ring of regular expressions exist?

It is well known that the set of Regular Expressions R over some alphabet form a semiring with: Concatenation as multiplication The empty string as the multiplicative identity 'Or' as addition The ...
3
votes
2answers
192 views

prove or disprove if the following language is regular language

for $A,B\subseteq\{0,1\}^*$ regular languages prove or disprove that $L_2$ is a regular language: $L_2 = \{x \in A | \exists y \in B : |x|_1 =|y|_1 \}$ $|x|_1$ means the number of appearances of 1 ...
0
votes
1answer
7 views

How to prove that $L=\{w\in\{0,1,2\}^*|\#_2(w)<\#_0(w)\}$ is not regular using Myhill–Nerode theorem?

How to prove that $L=\{w\in\{0,1,2\}^*|\#_2(w)<\#_0(w)\}$ is not regular using Myhill–Nerode theorem? $\#_2(w)$ means the number of occurrences of $2$ in $w$, same goes for $\#_0(w)$. I thought ...
0
votes
1answer
23 views

How to connect DFA state which had no transitions after minimizing it?

I have the following DFA, let it be $A$: The problem asks to find the minimal connected DFA for $A$, it is as follows according to the solution (the state $\{d,e\}$ is called $e$ for simplicity's ...
1
vote
1answer
21 views

How to find a DFA for combinations of even and odd occurrences $0,1$?

Let $L$ be a language over $\{0,1\}$ whose Nerode equivalence classes are: $$ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=0\}\\ \{w|\#_0(w)\mod2=0\quad\land\quad \#_1(w)\mod2=1\}\\ \{w|\#_0(w)\...
2
votes
1answer
38 views

How to find the equivalence classes of a formal language complement?

Let $L=\{\sum^*-(\{\epsilon, a,b\}\cup \{bba^i|i\ge 0\})\}$ be a language over $\sum=\{a,b,c\}$. Find the equivalence classes of relation $R_L$ which is defined as follows: $xR_Ly \iff \forall z\in \...
0
votes
1answer
32 views

How to find equivalence classes for $R_L$ for the language of words that begin and end with $aa$?

Let $R_L$ be a relation such that: $xR_Ly \iff \forall z\in \sum^*:xz\in L \iff yz \in L$. Find the equivalence classes for $R_L$ for this language: $$ L=\bigg\{w\in \sum^*\bigg| w\quad \text{starts ...
1
vote
1answer
46 views

PDA: Symbol in first half

How do I construct a PDA where: $L = \{w \in \{0, 1\} ∗ : |w| \text{ is even and } w \text{ contains at least one 1-Symbol in the first Half}\}$ To me it seems impossible to know when I reached the ...
2
votes
2answers
51 views

Proof for equivalence of two regular expressions

I have to show via equivalence transformation, that these two regular expressions are equivalent: $$(ab+b^*a^*) = (a+b^*)(a^*+b)$$ Can someone give me a hint how to show this? I am only allowed to ...
0
votes
1answer
24 views

$A,C$ are recursive and $A\cdot B = C$, Is $B$ is recursive?

Past year paper question. Prove or disprove: Suppose $A,C$ are recursive and $A\cdot B = C$ (The dot denotes concatenation). Then $B$ is recursive. I think it is false. Let $B$ be any non-recursive ...
3
votes
0answers
27 views

Searching for a proof for a variant of the pumping lemma for context free languages

So I'm trying to understand the pumping lemma for CFL ( context free languages ).I've already used it to show that a language is not contextfree and I have considered the proof of this lemma (see the ...
1
vote
1answer
21 views

Show that the following language is context-free/not context free by expressing the language as the union of three other languages.

I want to show that the language $L = $ {$a^mba^nba^p:m=n $ or $n = p$ or $m = p$} is either context-free or not context free by expressing the language as a union of three other languages $L_1$, $L_2$...
0
votes
1answer
34 views

Show that $L=\{a^nb^m : m \neq n\}$ is context free language using closure under union.

I'm trying to solve the following problem. I am asked to show that $L = \{a^nb^m : m \neq n\}$ is context free by expressing this language $L$ as the union of two other context-free languages. ...
0
votes
0answers
13 views

A relation of Kolomogrov complexity

Given a positive strictly monotonically increasing infinite sequence $n_1, n_2, \dots$ with Kolmogorov complexity $$K(n_i)\geq\lceil\log_2 n_i\rceil/2\,.$$ If $q_i$ is the greatest prime number that ...