Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
0answers
21 views

Make the language of First Order Logic uncountable

The question is in regards to The Lowenheim-Skolem theorem and the question asks to give a set of sentences that is only true in an uncountable domain. My teacher told me to solve this by "relaxing" ...
0
votes
1answer
21 views

is there a linear bounded automaton the decides $A_{nfa}$?

first post here :) I was wondering, since regular languages are context sensitive, and since linear bounded automatons can act as an acceptors for context sensitive language, is it possible or is ...
0
votes
0answers
9 views

Show that no Büchi Automaton with less than 3 states exists for the LTL formula $ G(p_1\rightarrow XFp_2) $

Given the LTL formula $ G(p_1\rightarrow XFp_2) $, show that there is no Büchi-automaton which recognizes the same set of $ \omega $-words $ \alpha \in (\{0,1\}^2)^\omega $ with less than three states....
0
votes
0answers
27 views

How would the Regular Expression (01*)* expand into a set? [closed]

What does the regular expression $(01^*)^*$ expand to a set? I think it would be something like: {λ, 01, 011, 0111, ... , 00, 010, 0110, 0101, ... } If so, can you explain why this is? I am not ...
0
votes
1answer
21 views

The formal language $L$ is regular iff there is a “reduced” NFA

I would appreciate some help for the following exercise: $L$ is a regular language if and only if there is a "reduced" NFA $N=\langle Q,A,\Delta, q_0,F\rangle$ with $L=L(N)$. With reduced I mean ...
0
votes
2answers
77 views

Variables and Language

I've been thinking lately about the kind of language we use when doing math involving variables. Consider a typical variable defining statement: "Let x = 2." If we try to parse this statement ...
0
votes
0answers
25 views

What is the closure property in this case

There is requirements specification which has certain Completeness properties: No "To be done" phrases No references to non-existing items No missing items No missing functions No missing products ...
1
vote
2answers
14 views

SAT for a formula using Tableaux Propositional Logic (precedence of operators)

My doubt is in check if the following formula $\phi$ is SAT or not using the Tableaux Method. Let me write formula: $\phi = \neg \left ( p \vee q \supset \left ( \left ( \neg p \wedge q \right ) \...
0
votes
1answer
56 views

How to define the class of terms of a formal language?

Suppose we have a language $\mathfrak{L}=\{\bf{C},\bf{P},\bf{F},\#\}$ consisting of constant, predicate, function symbols and an arity symbol for functions, $\#$, with alphabet $\Sigma(\mathfrak{L})$. ...
3
votes
1answer
58 views

Codification of a formal language in set theory.

Starting with an arbitrary class of sets $\Gamma$, can you generate a free semigroup $\Gamma^*$ over $\Gamma$ with the group operation of concatenation ($\frown$)? The goal here is to codify a formal ...
0
votes
1answer
44 views

Creating my own “Category Diagram Database” with query language.

Neo4j and other graph database software out there for one don't support subgraph isomorphism search out-of-the-box which is what I need and I'd also like full expressivity of a CFG on label matchings ...
1
vote
1answer
25 views

Non automatic structure, which is decidable

I know that $(\mathbb{N}, \cdot)$ and $(\mathbb{N}, |)$ are non automatic, but also not decidable. I also now that every automatic structure is decidable. Now I am curious if there is a non automatic ...
2
votes
1answer
23 views

How to define a certain language

Suppose we are given a binary function symbol $*$ and a countably infinite set of variables and also a pair of parentheses. In most logic textbooks, they have a rule that says that $(A * B)$ is well-...
0
votes
1answer
46 views

Difference of two decidable languages?

I've been learning about TMs in class lately and we talked about the decidability of two languages by union or intersection. I was wondering if you have two decidable languages, L1 and L2, is their ...
1
vote
1answer
51 views

A question on the formality of a theory

I've just about finished reading Mathematical Logic, Kleene, and I had a question about how theories are formed in formal logic. Throughout the beginning of the book he builds propositional and ...
2
votes
1answer
34 views

language kleene star union not equal to union of language kleene star

Find languages A and B such that $A^* \cup B^* \neq (A \cup B)^*$. Is this even possible? I tried: $A:\{$ $\epsilon $ $\}$ and B:$\{$ $1$ $\}$ $A^*= \{\epsilon \}$ and $B^*=\{\epsilon,1,11,111,.......
1
vote
1answer
20 views

concatenation of 2 non-context-free languages that is context-free but not regular

I'm having today a test on formal language theory, and I've seen a question about it I'm having hard time solving. The question is: Give an example of 2 languages, L,M which are non-context-free but ...
0
votes
0answers
34 views

Help with a proof using the pumping lemma

I am confused with even starting the proof. I understand the pumping lemma: Let A be a language over $\Sigma$. If A is regular, then there exists $p > 0$ (pumping length) such that $∀s∈A$, if $|...
1
vote
2answers
44 views

How many essentially different strings are there of length $\leq n$ and over an alphabet of size $|\Sigma| = m$?

For example, $aaaaaabb \simeq ccccccdd$ essentially, because a smallest grammar algorithm would perform the exact same steps to reduce one as the other. So how can I phrase this in terms of formal ...
0
votes
1answer
53 views

Metalanguage of mathematics

What excactly is the matalanguage of mathematics? I mean, the predicate calculus admits the formal language of mathematics, right? Then we add set axioms to it et voilá: mathematics. But what does ...
1
vote
1answer
79 views

Proving that Every Full Prefix-Free Language is Maximal

I'm practicing a problem where I need to prove that every full prefix-free language is maximal. I know a prefix-free language A is maximal if it is not a proper subset of any prefix-free language, ...
0
votes
2answers
45 views

Proof of A = {0, 1} and B ⊆ {0, 1}*

//Note that the "*" is the kleene star. Prove: If A = {0, 1} and B ⊆ {0, 1}* , then A* = B* ⇒ A ⊆ B. I will prove these two statements separately. First I'm proving A*=B* by showing that A*⊆B* ...
1
vote
2answers
47 views

Pumping lemma, L={WW^R | W can be {1}+}

im trying to find out, if L is regular or not using pumping lemma. I have L={WW^R | W can be {1}+} So possible strings would be 11, 1111, 111111. In every cases i have googled so far are examples ...
0
votes
1answer
90 views

How to find all the equivalence classes of a given language without using the Table-Filling-Algorithm.

I'm trying to solve an exercise problem for my formal languages class, that's to do with the Myhill-Nerode Theorem for regular languages. I'm given the following information and asked to find out all ...
0
votes
1answer
30 views

What is the right quotient of a language with itself?

This may be a really trivial question but I just want to make sure: if $L$ is some language then $L/L=\{\epsilon\}$ if $\epsilon \in L$ or $L/L=\{\emptyset\}$ if $\epsilon \notin L$? Does the same go ...
2
votes
2answers
29 views

Give an example of a language $L$ where $\min(\max L)\neq \max(\min L)$

Give an example of a language $L$ where $\min(\max L)\neq \max(\min L)$. I thought of the following language $L=\{a,bc, abc\}$. $$ \min L=\{a,bc\}, \max L = \{abc\} $$ Then: $$ \min(\max L)=\min (\{...
0
votes
0answers
31 views

How to prove that concatenation of words from regular languages is a regular language using left quotient?

Let $$ L=\{x\in \Sigma^*\big|x=uvw, \\u,v,w \in \Sigma^*,\\u\in L_1,\\v\in L_1,\\uw\in L_2\} $$ where $L_1, L_2$ are regular languages over $\sum^*$. Prove that $L$ is also regular. I'd like to ...
1
vote
1answer
29 views

How to disprove that the union of all non-context-free languages over $a$ is also non-context-free language?

This is the proof I came across: $L=\{a^{x^j}|j\ge 0, 2\le x\in \mathbb N\}$ is a non-context-free language. Suppose otherwise, then let $n$ be the constant promised in the pumping lemma. Let's ...
0
votes
1answer
47 views

Pumping Lemma - unregular expression

How do prove that this expression is unregular, I know firstly you have to try prove that it is regular and work from there. I also know that $w=xuz$ and the three rules are needed Let $M$ be the ...
0
votes
0answers
36 views

Context-Free grammar - Normal form

Termials = a,b,c. non-Termials = A,S. Production Rules: (1) S → aS (2) S → bA (3) A → bA (4) A → cA (5) A → c (6) S → a How do you write the following in normal form, I understand that it is ...
0
votes
1answer
51 views

Formal Languages - Context Free Grammar

Describe the formal language over the alphabet { a,b,c } generated by the context-free grammar whose non-terminals are 〈 S 〉 and 〈 A 〉 , whose start symbol is 〈 S 〉 , and whose production rules ...
1
vote
1answer
52 views

Questions about basic logic (why position of “for all” makes difference)

I am reading Appendix B of "Introduction to Analysis by Arthur Mattuck 1st edition" It says that the following two sentences have different meaning. The book says that if the epsilon is introduced ...
0
votes
0answers
17 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
22 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
vote
1answer
43 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
58 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
20 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
26 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
34 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
31 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
62 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
74 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
30 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
30 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
41 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
32 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
35 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
34 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.
2
votes
2answers
57 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
39 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 ...