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

1
vote
1answer
29 views

In formal languages, why is $L^0 = \{ \epsilon \}$? Why isn't it the empty set ∅?

It just doesn't make logical sense to me that a language to the power of $1$, is itself, but to the power of $0$ is only a tiny part of itself (since every language contains $\epsilon$) Wouldn't it ...
3
votes
1answer
68 views

What is this semi-circular symbol in the middle of a formula?

I have tried every search term I can think of but I can find no way of knowing what this symbol between the (a) and the trP means: Some context here, Point 2 in the third paragraph. Original image ...
0
votes
1answer
26 views

Context-free language or not

It is language: $L = \left\lbrace a^ib^jc^kd^l \mid i+k < j+l+3 \right\rbrace$ Is it context-free or not? I have two versions: 1)Pumping lemma(refute): get a word $uvxyz = aabcd$ if $i=2$ we get ...
0
votes
1answer
53 views

How can I prove this statement about square root?

Introduction In computer science there is a field called Formal Methods and Specifications. In this field software designers design softwares by specifying their functionalities in formal methods, ...
0
votes
1answer
45 views

Transition diagram for DFA's.

I have a homework question that asks to draw the transition diagram for the following: Draw transition diagrams for the DFAs below for the following languages. The alphabet Σ in this example is ...
-2
votes
1answer
18 views

Describe briefly the interrelationships that exist between, LRGs, Regular sets and DFAs [closed]

This question has appeared in a number of papers related to my current module in college. Would anyone be able to answer it? Thanks.
1
vote
1answer
39 views

Left and Right hand associativity equivalent first order logic

Say we are in a first order theory, and one of our inference rules is the associative rule saying that we can infer $(A \vee B) \vee C$ from $A \vee (B \vee C)$. Using the other logical inference ...
1
vote
0answers
17 views

Showing that language $L^{'}$ is regular given $L$ is regular [duplicate]

Say $L \subseteq \{a,b\}^*$ is a regular language with words whose length is divisible by 3. Each word $w \in L$ has the form $w=xyz$ with $|x|=|y|=|z|$, where $y$ is then called the middle third of ...
1
vote
1answer
57 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
0
votes
0answers
16 views

Pumping Lemma for Regular Language (Is my answer correct)?

I've been working on understanding the Pumping Lemma for 2 days now and I feel like I may have finally got somewhere. I was hoping to show you guys a question and my working out and if you think i'm ...
0
votes
1answer
19 views

On the existence of a non-regular language $L$ such that $L^2\in \text{Reg}$?

Is there a non-regular language $L$ such that the language $L^2$ is regular? Nothing comes to my mind. What's your proposition ?
0
votes
1answer
22 views

Showing that calculus are (not) equivalent

Let $\mathcal{A} = \{ x,y \}$ be an alphabet. Consider the following rules for derivation: $R_1 : \begin{array}{c} \hline \epsilon \end{array},\\R_2: \begin{array}{c} z \\\hline zx \end{array},~ R_3: ...
0
votes
0answers
19 views

Check if language is context free

The language is the set of finite prefixes of the infinite word: $a^1b^2a^3b^4 \dotsm$ The question is to show that this language is not context-free. So to my eye, it is not context free, let $p$ ...
1
vote
1answer
24 views

Prove the following language is not regular using pumping lemma.

Prove the following language is not regular using the pummping lemma $L = \{a^{n!} \mid n\geq0, n\in\ \mathbb{N} \}$. What I have done so far is: Assume $L$ is regular. So, there is a $DFA$ for $L$ ...
-1
votes
1answer
40 views

Describe a PDA that accepts the language L = {w | w = a^n b^n c^n , N > 0}

I was wondering could somebody give me an idea on how to answer this. This computation should start with an empty string >q0---->q1. How does the stack be incorporated into this question? sorry, new ...
0
votes
2answers
39 views

Describe as a regular expression the set of strings over {a,b,c} that contain the substrings aa,bb,cc

What would be an appropriate regular expression for this set of strings listed in my title? i have this so far: (aa,bb,cc) is a subset of all the strings listed (a,b,c) (it corresponds to the strings ...
0
votes
1answer
29 views

Graph and language/automaton equivalence

I'm looking for a reference rather than an answer. I think I'm just not Googling the right combination of terms. I imagine that there is a class of graphs which is equivalent to some class of ...
-4
votes
1answer
52 views

Let $A = \left\{{11,00}\right\}$. Find $A^n$ for $n = 0, 1,3$

I need to answer this question but I am struggling to understand what I need to do here, any help will be greatly appreciated!
0
votes
2answers
21 views

Examples of undecidable languages contained in 1*?

I've been given the following question Show that there is an undecidable language contained in $1^*$. But I can't think of any undecidable languages that are contained! Can someone please lend a ...
1
vote
1answer
17 views

Pumping Lemma proof and the union/intersection of regular and non-regular languages

I am still learning the pumping lemma. I have a problem for which I used it. I used it on the first part (a) but I am unsure if it is correct. Parts b-d, I am not sure how to do it. I created a dfa ...
0
votes
1answer
17 views

Context Free Grammer (CFG) for a language

Consider the language above $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y : x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need define a CFG for this language. I've tried couple of ...
0
votes
1answer
50 views

Context-free languages closure property

Trying to rove that the set of all context-free languages over a language Σ is closed under TRIPLE where TRIPLE (L1, L2, L3) = L1L2L3. Pretty much, TRIPLE, applied to three languages yield the ...
0
votes
2answers
40 views

Dollar Sign in Context Free Language

I have a homework about find the pumping lemma in Context Free Language. The last one I couldn't solve: $L = \{a^i \$ a^{3i} \$ a^{5i} \mid i \in \mathbb{N} \}$ What does the dollar symbol mean ...
2
votes
1answer
40 views

Is this language context-free or not?

I have a problem to solve, the problem is: Is the language of strings $$L=\{0^x1^y:x\nmid y\}$$ context free? I suspect it isn't, I spent some time trying to make a grammar that could ...
0
votes
1answer
15 views

Proving regular languages

I am given the language L = {a,b}* and a/L = { w ∈ {a,b}* | aw ∈ L }. I am trying to prove that that if L is regular so is a/L. My approach so far is the prove that L is regular (using pumping lemma) ...
2
votes
1answer
67 views

Why are structures with no relations called algebras?

"If [a given structure] A has no relations it is termed an algebraic structure, or simply an algebra" - Wolfgang Rautenberg, A Concise Introduction to Mathematical Logic, 3rd edition, page 42. I ...
1
vote
1answer
21 views

Repeated rules in Chomsky normal form

My question is simple, when you're converting a grammar to CNF, what happens when a rule begins to repeat multiple times? ¿It's good to end with rules like $U_1 \rightarrow SB, U_2 \rightarrow SB, ...
0
votes
1answer
39 views

context-free languages operation closure

The following operation is defined on formal languages. $ operation1(L) = \lbrace w \ | \ wxy \in L, \ \forall x \forall y \ (|x|=|w|) \ \wedge (|y| = |w| ) \rbrace $ Prove that context-free ...
1
vote
1answer
27 views

Is $L = \{0^{i}1^{i}0^{j}1^{i} | i, j > 0\}$ a context free language?

Is the following argument correct? $L = (A \circ B) \cap C$ where, $A = \{0^{i}1^{i}$ $|$ $i > 0\}$ $B = \{0^{j}1^{i}$ $|$ $i, j > 0\}$ $C = \{0^{i}1^{j}0^{k}1^{i}$ $|$ $i, j, k > 0\}$ We ...
2
votes
1answer
29 views

Show that language is context free

Show that language is context free $E=\{a^ib^j|i\neq j\wedge 2i\neq j\}$ Look at my solution please: I use the fact that languages context free are closer under sum $E=E_1\cup E_2\cup E_3 = ...
0
votes
1answer
57 views

Creating a language

I am given a list languages, say $L$, over alphabet $\{a,b\}$. A function $f$ is defined such that $f(i) = L$ for $i ∈ N$. I am trying to a construct a language $D$ which is not in the list (aka. $D ...
1
vote
1answer
34 views

Proving with pumping lemma

I am trying to prove that the follow language is not regular L = {w ∈ {0, 1}∗ | the number of 1s in w is one more than the number of 0s} My approach was to prove that it is regular and prove by ...
1
vote
1answer
42 views

Formal language: Proving the reverse operation on a word through induction

I'm practicing proofs and given the following statement: Let $\Sigma$ be an alphabet, $\epsilon$ the empty word and $\sigma:\Sigma^{*}\rightarrow\Sigma^{*}$ an operation which for $a\in\Sigma$ and ...
0
votes
0answers
30 views

Adding Sentence Variables and Quantifiers to Formal Languages

I have been thinking about the following construction, and was contemplating investigating it for my undergraduate thesis: Let $L$ be a formal language, e.g. the set $\{x_1, x_2, \dots, \forall, ...
2
votes
2answers
41 views

A Regular Expression for all strings that…

I got a problem I have to solve, the problem says that given an alphabet $\Sigma = \{a, b, c\}$ I have to build a regular expression that describes the string with: An even number of a's. A 4k + 1 ...
2
votes
0answers
58 views

How to show $L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ is ambiguous?

I'm recently familiar with this site and prefer to ask a very hard problem :) How can we prove that the following language is inherently ambiguous? $$L = \{a^n b^m c^p: n\neq m\} \cup \{a^n b^m ...
1
vote
1answer
45 views

Is it possible to write an Unambiguous Grammar for Two Hard Language ?!?

I came across a very hard interview exam. It was asked wrote an unambiguous grammar for two following language, Who can hint it to solve it? 1) $L = \{a^n b^{2n} c: n\geq 0\} \cup \{a^{2n} b^n d: ...
1
vote
1answer
52 views

Sentences, Formal Grammars with derivation (parse) trees

I've been reading / studying formal grammars for the past few weeks and I came across a question that puzzled me and I cannot seem to get my head around it for some reason. ...
0
votes
1answer
53 views

How to prove the language of all binary numbers that are prime is nonregular using pumping lemma?

How to prove the language of all binary numbers that are prime is not regular using pumping lemma? I have seen Can an infinite set of primes be a regular language or CFG? We have not studied the ...
0
votes
1answer
29 views

Negating multi-layered statement regarding a formal language

I'm having trouble negating a nested statement. Let $\Sigma$ be an alphabet, $L\subseteq\Sigma^{*}$ a language and $n\in\mathbb{N}$ a natural number. For all words $x\in{}L$ with $|x|\geq{}n$ there ...
0
votes
2answers
29 views

Proving that the set of languages over an alphabet Σ is a monoid regarding concatenation

I'm practicing proofs and would like to prove that the set of languages over an alphabet $\Sigma$ is a monoid regarding concatenation by showing that the following statements are true: There is a ...
0
votes
0answers
40 views

how can i find a grammar for this language?

The language is $L = \{a^i b^j c^k | k = (i + j)^2, i > 0, j > 0\}$. To produce a's and b's I have this solution: S -> aS | aB B -> bB | bC but for producing the right number of c's i have no ...
2
votes
1answer
26 views

Pump lemma. Usage.

Let $A$ be DFA and $B$ be DFA. Let $K$ be an alphabet and $L(A) \subset K^*$ and $L(B) \subset K^*$ Prove that there exists such $p \in \mathbb{N} $ that, if for every $w \in K^*$ where $|w| \le p $ ...
-1
votes
1answer
19 views

Necessary and sufficient condition so that L be equal to L*

Given L a formal language, what are the necessary and sufficient conditions so that L = L* Definition of L* is: $$ L^*=\bigcup_{i\in \mathbb{N}_0}L^i=L^0\cup L^1\cup L^2\dots $$
0
votes
1answer
57 views

Learning finite automata from symbol set and given sample

Good day. We have a finite automaton F1, for example, . We need to get automaton F2 that accepts strings like accepted by ...
0
votes
1answer
60 views

Pushdown Automata formal definition, L(M), tracing input

Let M be a deterministic PDA with the transition function d: ...
3
votes
5answers
161 views

What is the difference between the relations $\in$ and $\subseteq$?

Don't they both mean that something is an element of a set? Are they interchangeable in some or all situations? Like: $x \in A$ ($X$ is an element of the set $A, X$ is in $A, A$ contains $X$) $x ...
0
votes
2answers
48 views

How can metalanguage be a formal language?

It is said metalanguage is a formal language. If this site about computer science is right (http://interactivepython.org/courselib/static/thinkcspy/GeneralIntro/FormalandNaturalLanguages.html), formal ...
2
votes
1answer
21 views

Languages and their relation : help

This is not a homework question though, this is something I wish to know to add to my own knowledge. While reading one of the texts on automata (K.L.P. Mishra, "Theory of Computer Science : Automata, ...
0
votes
0answers
27 views

There exists a descending chain of symmetry groups from a formal language string down to its smallest grammar.

Background. Let $\tau \in G_i$ be a permutation in the symmetry group of the smallest grammar $g_i$. Then $\tau$ permutes each set of positioned (within $g_i$) symbols $\{x_1^{(1)}, x_1^{(2)}, \dots, ...