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.

Filter by
Sorted by
Tagged with
0
votes
1answer
9 views

Prove or disprove: If A is regular and A ∩ B is not regular, then B is not regular.

I suspect the Myhill–Nerode theorem may come into play, but not certain. If this was a union instead of an intersect, I'd be almost 100% sure it was true. I'm relatively confident that this statement ...
2
votes
1answer
19 views

Prove or disprove: If A and A ∩ B are regular, then B is regular.

I suspect the Myhill–Nerode theorem will come into play, but not certain. If this was a union as opposed to an intersect, I'd be pretty confident that this would be true, but with it being an ...
2
votes
1answer
30 views

How to proof $\text{if } {B \subseteq A} \implies A^*B^* = A^*$

For context, A and B is a regular language, and related to Theory of Computation. As the title says, it is so intuitive that $$ \text{if } {B \subseteq A} \implies A^*B^* = A^* $$ I don't know how to ...
-2
votes
0answers
13 views

DFA set builder problems [closed]

Write L in set builder if the language only has an English descrption. Write L complement in set builder Please find the link of the questions below. DFA questions Link
0
votes
1answer
39 views

How can any sentence be valid?

I've just started working through C. Chang and H. Keisler's Model Theory independently right now, and I'm reading through the first chapter, but I'm a little confused by the nature of a valid sentence....
1
vote
1answer
25 views

$(a \lor b) a a^*(a \lor a a^*b) \lor (a \lor b)aa^*aa^*$ is wrong?

Here is the non-deterministic finite automaton. I want to find the reguluar expression related to this diagram. I found $(a \lor b) a a^*(a \lor a a^*b) \lor (a \lor b)aa^*aa^*$, but it seems my ...
1
vote
0answers
37 views

$(a \lor b)(b(a \lor b))^*$ is wrong?

I have to find the regular expression of this finite automata. I guess I could get rid of the trash state. I got $(a \lor b)(b(a \lor b))^*$, but it seems to be wrong and I can't say why. Can you ...
1
vote
1answer
32 views

$01^*01^*(0 \lor 1)^* \lor 10^*10^*1(0 \lor 1)^*$ is wrong

I have the following finite automata. I would like to know its regular expression. I gave $01^*01^*(0 \lor 1)^* \lor 10^*10^*1(0 \lor 1)^*$, but it seems my answer is wrong. Can you tell me why?
0
votes
1answer
27 views

Kleene Star over a formal Language containing Unions

I am a little bit confused, how the following language should be understood or further more, how the Kleenestar is interpreted in some ways: $ ( \{0\} \cup \{1\}^*)^*$ I think the language looks like ...
1
vote
2answers
70 views

Can someone help me identify this math symbol and its meaning?

From my university notes: Comment to slide 9 By virtue of the result shown in this slide, we can talk about the least element of a set $D$, if one exists, and we denote it with $\perp$, pronounced &...
0
votes
1answer
26 views

Shannon entropy of languages

In his paper Prediction and Entropy of Printed English Shannon defines the entropy $H$ of a language as $$H = \lim_{N \to \infty} F_N$$ where $$F_N = \sum_{i, j} p(b_i, j) \log p(j | b_i)$$ where $b_i$...
1
vote
1answer
31 views

Prove whether a language is finite or infinite.

Consider the language : $L = \{w \mid w \in \{0, 1\}^∗, w \text{ has three times as many }1\text{'s as }0\text{’s}\}.$ Say whether $L$ is finite or infinite, and prove that you are correct. I am ...
1
vote
1answer
38 views

Combining two DFAs into 1 DFA using concatenation [closed]

L= { w : w has exactly two a's and at least two b's} Picture of DFA's https://i.stack.imgur.com/4mPHU.png I have made the two DFA's separately, but I am having trouble combining them specifically the ...
8
votes
0answers
167 views

Unambiguous formal grammars for a specific class of languages

Suppose that $w \in \{0; 1\}^*$ is a binary word. Let's denote the number of $0$-s in $w$ as $\#_0(w)$ and the number of $1$-s in $w$ as $\#_1(w)$. Now suppose that $q \in \mathbb{Q}$ is a positive ...
2
votes
3answers
75 views

What does it mean to find something in Set theory? What is formal-language equivalent of “find”?

For example in proof that every real number $x$ has a decimal expression $x=a_0.a_1a_2a_3….$ it says: so we can find $a_1$ between $0$ and $9$ such that... https://math.stackexchange.com/a/2625318/...
1
vote
1answer
26 views

Prove that the unitary PCP is decidable.

Prove that the unitary PCP (Post Correspondence Problem where $\vert \Sigma \vert = 1$) is decidable. Case $1$: If a tuple $(x_i, y_i)$ with $\vert x_i\vert = \vert y_i\vert$ exists, then the answer ...
0
votes
1answer
21 views

How to show that a set is not in PCP (Post Correspondence Problem)?

In my lecture slides I have two examples of sets of tuples, where the first one is in PCP while the other one is not. The first is: $$PCP:=\{<(x_1,y_1)=(1,101), (x_2,y_2)=(10,00), (x_3,y_3)=(011,...
2
votes
1answer
18 views

Beta Reduction Constraints

The definition of $β$ reduction is the following : $$(λx.M)N \rightarrow_{β} Μ[x∶=N] $$ So basically we stop treating $x$ as a bound variable and we perform substitution of the now free variable $x$ ...
0
votes
0answers
20 views

Use a proof by contradiction that for any A⊆Σ*, the concatenation A∅ = ∅.

I want to know how to prove with contradiction that for any A is a subset of a finite set, then the concatenation of A∅ = ∅.
-1
votes
2answers
78 views

Write the contrapositive of “if $n$ is an even integer such that n + 1 is a square then n is divisible by 8”

For the purpose of clarity, I do not want anybody to prove this statement, I am just looking to get some help translating it into the contrapositive using symbolic logic. Right now I have the ...
0
votes
1answer
46 views

What does $\{0 , 1\}^+$ mean?

I'm trying to do an assignment in my theory of computation class, and its talking about some abstract mapping $\sigma$ as defined $\Sigma^+ \mapsto \Sigma^*$. I am familar with what $\Sigma^*$ means, ...
0
votes
0answers
45 views

Show that a set is countable by specifying an alphabet for it

Consider the set $S = \{ \sqrt n \mid n \in \Bbb N_0\}$ This is a countable set certainly as we can produce a simple one-to-one function for this set to natural numbers. But I want to do it another ...
1
vote
1answer
22 views

The smallest set of well formed formulas in Tourlakis' Mathematical Logic

In page 13 of Mathematical Logic, Tourlakis defines the set of all well-formed-formulae as: ... the smallest set of strings, WFF, that satisfies: 1) All Boolean variables are in WFF, and so are the ...
0
votes
0answers
19 views

Regular safety property

I have been studying model checking. I think my intuition is still poor as I'm having trouble checking whether a property is a regular safety one or not. For example, consider the following property, $...
0
votes
1answer
44 views

Explaining the difference between two definitions for recursively enumerable languages.

I'm a little confused about the definition for recursively enumerable languages in my script. A recursively enumerable language is defined as: A language $A \subseteq \Sigma^*$ is called recursively ...
0
votes
2answers
42 views

Formal definition of a complement of a language.

I am in the midst of learning decidable and undecidable language and I came across the following theorem: A language $A \subseteq \Sigma^*$ is decidable if and only if $A$ as well as $\Sigma^* \...
2
votes
1answer
46 views

Determine whether language L is regular

Let $L\subseteq \{0, 1\}^*$ be the set of natural numbers in binary notation, which together compose the infinite arithmetic progression with first term 4 and common difference 3. Is it true that $L$ ...
1
vote
1answer
33 views

Prove that the language L is regular

Let $\Sigma$ be the Latin alphabet ({a, b, c, ..., x, y, z} - 26 letters). Given the language L = {$\alpha \in \Sigma$*| if $\alpha$ has the letter a, then $N_a(\alpha)$ = 4 and if $\alpha$ has the ...
0
votes
0answers
11 views

Show that the “slowdown” in the use of k > 1 tape to k = 1 tape is not too significant.

We Let A be a language that can be decided in time T by a 2-tape Turing machine M2. Then there is a 1-tape Turing machine M1 that decides A in time O(T^2). Proof. We will sketch the proof for the case ...
1
vote
1answer
82 views

Context-free grammar (CFG)

How do I generate a context free grammar for a language $$\Sigma = \{0, 1\},\ L = \{1^i0^j1^k \mid i, j, k \geq 0\}$$ Thanks already
2
votes
1answer
44 views

Beta Reduction in Lambda Calculus

I came across the definition of beta reduction in Lambda Calculus which is : $$(λx.M)N \rightarrow_β Μ[\space x:= N \space]$$ under the constraint that the $FV(N)$ are still free after the ...
1
vote
1answer
26 views

Substitution constraints in Lambda Calculus

I came across this definition of Substitution in Lambda Calculus and I am trying to wrap my head around it.$$(λy.P)[x:=N] \equiv λy.(P\space[x:=N])$$ given two constraints : $y \notin FV(N)\space$ or ...
2
votes
1answer
49 views

Interpretation of a term in Lambda Calculus

Just started studying $λ$-calculus and I came across this $λ$-term : $$λx.λy.xy$$ As far as I understand this can be read as : Apply $x$ to $y$ The result of $(1)$ is probably an expression say $E_1$ ...
2
votes
1answer
40 views

Lambda Calculus Terms

According to what I've read so far a lambda calculus term is described as : $\langle term \rangle ::==$ $\langle var \rangle |\space (\langle term \rangle\space \langle term \rangle) \space |\space (...
0
votes
1answer
26 views

How do you show that the language L= { $ a^nb^nc^na^kb^lc^m : k,l,m,n >0 $ } is not a cfg?

I understand how for the language $ a^nb^nc^n $ it is a straightforward application of the pumping lemma, but the part after that seems to exclude the possibility of using the pumping lemma. I would ...
0
votes
1answer
57 views

Regular Expressions Theory Questions

I have some old exercises of regular expressions without solutions and i would like to check if i understand the theory correctly. In the methodology section i show my answers/steps so far. After the ...
0
votes
1answer
24 views

How to prove that the language of Non-palindromes is not regular (via pumping lemma)

I am trying to find that $L ={\{w\text{ | } w ∈ {\{a, b\}} * \text{is not a palindrome}\}}$ This is related to this previous question, though in this case I want to explicitly prove it via pumping ...
0
votes
0answers
40 views

How to Avoid Abusing the Terminology of Interpretations and Representations With Respect to Formal Languages?

I find myself floundering in terminology, with the result that I fear the article I am writing will only appeal to readers afflicted with masochistic tendencies. At the very least, there is the ...
2
votes
1answer
35 views

In a Discussion Involving Formal Languages, Can a Word Be Regarded as an “Expression”?

In order to avoid sounding repetitious by too frequently using the word "word," I would like to be able use the word "expression," writing, e.g., "Applying the function $f$ to ...
1
vote
0answers
10 views

Can an indexed grammar exclude a prefix from a postfix?

The problem is to define or prove the impossibility of defining an indexed grammar for the set of strings $A q B$ such that $A$ is at least one symbol and does not contain $q$ $B$ does not contain $q$...
0
votes
1answer
39 views

How do I create a context free grammar for a^k w where |w|=k [closed]

I've tried various combinations but can never get the length of w = k
2
votes
0answers
53 views

Grammar for homotopy type theory?

The HoTT book says: We will not attempt to give a formal presentation of the grammar of a valid inductive definition and its resulting induction and recursion principles and pattern matching rules. ...
-1
votes
1answer
131 views

How to add a column based on other columns in R [closed]

Suppose I have the data frame: table<- data.frame(seniority=c(1,2,3,4), sex=c(F,F,M,F)) Now I want to add a new column table$bonus with the values table$seniority*2 if the sex is "F", ...
1
vote
1answer
42 views

Using an Infinite Universe in a Formal Langauge Structure

I'm working through Leary and Kristiansen's "a friendly introduction to mathematical logic". When I get to page 23, they have introduced the idea of a formal language, along with the ...
0
votes
0answers
46 views

Writing CFG for Languages

Write a CFG for the given language L: L = { a^i * b^j * c^k | i=j or i=k. Consider i >= 0, j >= 1, k >=0 } I came up with: S → XY | W X → aXb | ε Y → cY | ε W → aW c | Z Z → bZ | ε
5
votes
0answers
44 views

What is the probability that a random regular expression defines the language of all binary strings $\{0, 1\}^*$?

Suppose we generate a random regular expression $R$ in the following way: We start with a single meta-symbol $S$. Then each turn we independently replace all $S$ in our word with $\{0\}$, $\{1\}$, $(S ...
2
votes
1answer
33 views

Why is it enough to test only the words up to length n ( number of state) in the given algorithm for a decidability problem

My question is related to the problem below, basically it's a decidability problem and the algorithm prooves it's decidable. My question : After reading the step 2 of the algorithm below, why is it ...
1
vote
1answer
45 views

Is Language of All Binary-Digit Strings Not Containing Substring 0100 or Suffix 010 Context-Free?

Let $\Sigma$ be the alphabet consisting of the symbols {0,1}, let $\Sigma^{*}$ be its Kleene closure, and let $R$ be defined by $R = \{w \in \Sigma^{*} \mid (0100 \text{ is not a substring of }w) \...
0
votes
1answer
51 views

Show these affirmations using the context-free pumping lemma properties

The question : Given $G$ a context-free grammar of Chomsky normal form with $k$ symbols. We know that the language $L(G)$ satisfy the pumping lemma for $ p = 2^k + 1$ I have those two questions to ...
1
vote
2answers
68 views

Prove that if $z^n$ is a palindrome for some $n>0$, then $z$ is also a palindrome for any alphabet E.

Prove that if $z^n$ is a palindrome for some $n>0$, then $z$ is also a palindrome for any alphabet E. Here's a proof of the statement above: Let $w = x^n$. If $n = 1$, then the result is trivial. ...

1
2 3 4 5
35