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

2
votes
2answers
47 views

Finding a grammar for given language

So for this problem we are given a language and we have to find the grammar for that set. I am confused and what the constructors should be. The language in this problem is: $\{bb, bab, baab, ...
0
votes
0answers
38 views

Are these proofs all right? (Automorphism group of a string).

Background. Let $G$ be the automorphism group of a string $s$, ie. $G = \langle (i,j) : i \lt j, s[i] = s[j]\rangle$. Then $G$ is a normal subgroup of $S_{|s|}$ the symmetry group on $|s|$ symbols. ...
0
votes
1answer
43 views

Proving an operation is closed under regular languages

Following operation is defined over languages where $n \in \mathbb{N} :$ $L \ominus n = \lbrace s \in \sum^* | \exists s^{'} \in \sum^* (length(s^{'})=n,ss^{'} \in L) \rbrace$ Meaning that $L ...
1
vote
1answer
51 views

Finite groups acting on strings.

Let $s = abcdandsoon.. \ \in \Sigma^*$. Let $|s| = n$ be the length of $s$. Consider all permutations of the positioned symbols that make up $s$, such that $s$ is fixed under the permutation. So if ...
-1
votes
2answers
25 views

Decomposing an infinite regular language

Let $L$ be an infinite regular language. Prove that $L$ can be split up into $L_1, L_2$, so that $L_1 \cup L_2 = L$ and $L_1 \cap L_2 = \emptyset$ Can you give me some directions to do it? Thanks ...
0
votes
1answer
104 views

Proving some property of a Formal Logic Language [duplicate]

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq ...
1
vote
2answers
131 views

Proving a property of a Logic Formal Language

I am stuck at this problem: Let $\Sigma = \{\lnot,\lor,\land,\rightarrow,\leftrightarrow,(,),P_1,...,P_n\}$ be an alphabet. Now let's define the set of logical expressions $\mathscr{L} \subseteq ...
1
vote
1answer
80 views

What is to define truth in Mathematical Logic?

Tarski's Undefinability Theorem says that arithmetical truth cannot be defined in arithmetic. What is the meaning of "definition"? Is it formal?
0
votes
0answers
39 views

How can symbols be formulated in metalanguage?

In Tarski's Undefinability Theorem, a definition by the name of "Convention T" involves symbols formulated in metalanguage. How is that possible? Shouldn't symbols be exclusive to formal languages? ...
1
vote
0answers
42 views

Context free grammars for generating mathematical expressions

I am looking for some resources on CFGs capable of generating mathematical expressions. For example an expression like the one below $expression = a + 2b + 4ac$ Where a,b,c are some terminal ...
2
votes
2answers
122 views

Are there two non-regular languages whose concatenation is regular?

Here is my proof: Consider non-regular languages $$L_1 = \{a^i b^j | i \neq j\} $$ and $$L_2 = \{b^n a^m | n \neq m\}$$ Then the concatenation of these two languages would be $$L_1 L_2 = \{a^i ...
-1
votes
1answer
25 views

Prove that language $Y=a^p$ is not regular

Prove that language $Y=a^p$, where $p$ is prime is not regular. Look at my proposition - is it ok ? I use pumping lemma. Let's assume that $Y$ is regular. Let $s \in Y$. For this word we have ...
1
vote
2answers
62 views

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular (prime numbers)

Prove that the language $\{bin(p) \mid p\ \text{is prime}\}$ is not regular, where $bin(p)$ denotes the binary representation of $p$. I should use the pumping lemma. But I have a problem. Could you ...
2
votes
2answers
22 views

Deriving a Formula From a Simple Artificial Language

The three rules of the language are: The letters P and Q are sentences. If φ and ψ are sentences, then Nφ and (Iφψ) are sentences. Nothing else is a sentence. (no more information was given about ...
3
votes
0answers
57 views

Is regular following language?

I try to prove that the language $L$ is not regular: $$ L = \{w\in(a+b)^*:\#_a(u)>2009\#_b(u)\ \text{for every nonempty prefix u of word w} \} $$ Note: $\#_a(u)$ means the number of symbols $a$ ...
0
votes
4answers
65 views

prove that language is not regular (prime numbers)

$$\sum_{p\,\in\,\text{Prime}}(cb^*)^p + (b+c)^*cc(b+c)^*$$ Show that language is not regular. We see that there are two possibilities: $p$ (prime) blocks of $b's$ separated by $c$ or any string of ...
0
votes
1answer
25 views

prove that language $Y$ is not regular

$\sum=\{1, \#\}$ $Y=\{w| w=x_1\#x_2\#...\#x_k\ \ k\ge 0\ \ \ x_i\neq x_j\ \text{for}\ i\neq j \}$ Prove that language $Y$ isn't regular. I know pumpping lemma. Firstlty I don't understand this ...
2
votes
1answer
35 views

Examples for different types of formal languages

I'm looking for examples of formal languages for Chomsky Type-0 to Type-3. While it is very simple to find examples for Type-1, Type-2, and Type-3, it is extremely hard for me to construct a simple ...
0
votes
1answer
55 views

Proving Reversal of a Language in Recursive Way

We define the $reverse$ of a string as follows: $(x_1x_2...x_n)^R=x_nx_{n-1}...x_1$ where $x_1,x_2,...,x_n \in \Sigma$. We can also define the reverse of a language by $L^R= \lbrace s' | \exists s ...
1
vote
3answers
50 views

Show that a language is regular

Show that language $B$ is regular: $$B = \left\{1^ky\mid y\in \{0,1\}^*\right\} $$ $y$ contains $\ge k$ symbols $1$ So I try in following way - I'll draw DFA: What about my solution? Is it good?
0
votes
0answers
43 views

Intersection of 2 deterministic finite state automata, but nondeterministically

Starting from 2 simple deterministic finite state automata, I need to construct a non-deterministic automaton that accepts the intersection of the two inputs. Using the algorithm presented at ...
0
votes
1answer
24 views

help with set example

A given set: k= {L⊆ {0,1}* s.t. for all w∈L |w|≤ 3} What is the plot of this set? Is this correct? {{0,1,00,01,10,11,000,001,010,011,100,101,110,111}}
0
votes
0answers
66 views

Showing that Turing-recognizable languages are closed under union

I'm reading "Theory of Computation" by Michael Sipser and I've encountered a solution (provided by the book) that I don't understand. The question: Show that the collection of Turing-recognizable ...
3
votes
0answers
97 views

Converting a pushdown automaton (that accepts by final state) to a context-free grammar

Given the following PDA: $$ P = (\{q, p\}, \{0, 1\}, \{Z_0, X\}, \delta, q, Z_0, \{p\}) $$ where the transition function $\delta$ is given by: $$ \delta(q, 0, Z_0) = \{(q, XZ_0)\} \\ \delta(q, 0, ...
1
vote
1answer
36 views

Is the empty set/language contained in the following set

Assume I have the following set of languages: $$ \{L \subseteq \{0,1\}^* \mid \text{for all $w \in L$, $|w| \leqslant 3$}\} $$ I know it contains the language containing the empty word since the ...
2
votes
1answer
30 views

Language interpretation dilemma: How do I interpret this textual statement?

How do I interpret this statement? Given a set S containing n real numbers and a real number x, there are two numbers in S whose sum is x. It's not clear to me what we can assume here. I'm not ...
20
votes
3answers
2k views

Why is Gödel's Second Incompleteness Theorem important?

Given that the consistency of a system can be proven outside of the given formal system, Gödel says, It must be noted that proposition XI... represents no contradiction to the formalities ...
0
votes
2answers
50 views

Checking Understanding of DFA Regular Operations - Intersection and Star

I'm currently taking a Logics course, and trying to understand the regular operations, intersection and star. I have a question regarding the work I have done so far. Given the following ...
-1
votes
1answer
53 views

$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$ [closed]

Why the following is not context free? Anyone could describe it for me. $L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$
0
votes
1answer
29 views

Launguages in Discrete Mathematical Structures II

For the grammar $G$ specified, draw a derivation tree for each of the given strings or conclude that the string is not derivable from $v_0$. $G = (V, S, v_0 , \rightarrow ), \\ V = \{v_o, v_1, x, y, ...
1
vote
1answer
62 views

Define recursive function prefix.

I need to define a recursive function, over strings, prefix in that way $\mathrm{prefix}(x,y) = \mathrm{true}$ if $x$ is prefix of $y$. This is my approach so far: $\mathrm{prefix}([ ],y) = ...
0
votes
1answer
109 views

Context Free Grammar and some details [closed]

Why this grammar shows a Context Free and Linear Language, (i.e, not context sensitive or non-context free). S -> SBA | a BA -> AB aA -> aaB B -> b
3
votes
2answers
63 views

Is the language “substrings of an even-lengthed regular language” also regular?

I want to prove that for a regular language $L$ where $\forall w \in L$ the length of $w$ is even, the language containing the first halves of the words of $L$ and the language containing the second ...
0
votes
1answer
32 views

Regular Expression of alternative 0's and 1's?

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where $$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$ Is $(0)*$ + $(1)*$ a valid regular expression that represents this ...
1
vote
1answer
29 views

How to match this language with variables?

How can i go about representing this language in variables? (a) The language of all strings containing exactly two 0's. (b) The language of all strings containing 010 as a substring. My Approach: ...
2
votes
1answer
27 views

Concatenation of context free language and a maybe pointless theorem

In our lecture our professor claimed this result: Let $\{1,\dots,k\}$ be an alphabet (or terminals) for the context free grammar $\tau$, $L(\tau)$ is the language generated by $\tau$. Let ...
0
votes
1answer
121 views

Finite language proof involving finite automata

Question: Show that every finite language (including the empty language) is accepted by some finite automaton with exactly one final state How would I go about solving this? I tried my own approach ...
1
vote
1answer
107 views

Solving the conjugacy equation $xy=yx$ in the free monoid

I'm having some trouble on showing this: Let $\sum$ be a finite alphabet, $x,\ y \in \sum^{*}$. Show: $$(xy=yx) \iff \exists s \in \sum^{*} ,\ i,j \in \mathbb{N}, (x = s^{i}, y = s^{j})$$ If we ...
0
votes
1answer
41 views

Give context-free grammars for these languages(Need clarification for my answer)

I'm just looking to understand if my justification I wrote makes sense (it might not) in a) b). Note: I'm doing exercises from a textbook which has no solutions I can see. So I can't check my answer ...
5
votes
1answer
36 views

Formal Grammar generating $0^p$

Exercise: Find the formal grammar generating the language ${0^p}$ in the binary alphabet for $p$ prime. I have absolutely no clue where to start, nothing of the 'usual' construction strategies seem ...
0
votes
1answer
28 views

Closure properties between 2 languages of different types

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
2
votes
1answer
27 views

Concatenation of regular languages.

The concatenation of $L_1$ and $L_2$ denoted by $L_1.L_2$ = $\{uv|u\in L_1\,and\,v\in L_2\}$. If, $$L_1=\{a^n|n\geq0\}\,and\,L_2=\{b^n|n\geq0\}$$ Then why is $$L_1.L_2\neq \{a^nb^n|n\geq0\}$$ I am ...
0
votes
1answer
35 views

Lambda Calculus Reduction (applicative vs normal order)

I am a little confused to reduce these lambda calculus expressions. I am instructed to give applicative and normal order reductions for these expressions. (a) (λx. ((λy.(* 2 y)) (+ x y)))y (b) (λx. ...
4
votes
0answers
71 views

Vague predicates in standard predicate logic [closed]

I'm trying to work out if a sentence of the form: 'Bob is larger than Maureen and almost as large as Chris' can be adequately formalised in predicate logic. One could just write: ...
0
votes
2answers
93 views

Context free grammar for AN

I need to write Context free grammar for describing moves in a game of chess using the Algebric Notation. Can anyone help me get started. f.ex. how do I write this for this move: Bb5 Bd7.
1
vote
1answer
45 views

Difference between $\phi$ anf $\epsilon$ in regular language.

What is the interpretation of both $\emptyset$ and $\epsilon$ in a regular language? Do they both mean empty sets? If so then why is $\emptyset^*=\epsilon$ , $\emptyset^+=\emptyset$ and ...
0
votes
1answer
47 views

Final state of a Finite automaton.

Can a finite automaton not have a final state? For example, for the question "what is the number of states need to accept an empty language?" people answered that one state is enough to accept a ...
0
votes
1answer
54 views

Regular Language Problem?

Let L be the set of all strings that are not in the English language. Is L regular? From textbook, would like some help? Someone recommended to me to think about how regular and regular languages ...
0
votes
1answer
40 views

Proving language as regular

Suppose that A and B are languages such that A o B is regular. Suppose that B is regular. Prove or disprove that A is regular. I am having a tough time with questions relating to proving a language ...
0
votes
2answers
56 views

Proving L is a regular language?

I am having tough with problems like this. Can someone help me. Let L be the set of all strings that are not in the English language. Is L regular?