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

0
votes
1answer
19 views

Which is true about this NFA?

Let $M$ be an NFA with alphabet {0,1} that accepts every binary string. Which of the following is true? a) Every state of $M$ must be an accept state b) $M$ does not have any accept state c) The ...
0
votes
1answer
35 views

Backus-Naur Form with automata

Parsers & compilers usually utilize deterministic finite automata to parse input. It's very easy to implement a generic DFA tool, that simulates any DFA table for example to validate input. ...
0
votes
1answer
45 views

Determine the languages for the given alphabet

For the alphabet $\sum = \{0,1\}, let A,B,C \subseteq \sum^*$ be the languages below. $i. A = \{1, 0, 00, 11, 000, 111, 0000, 1111\}$ $ii. B = \{w \in \sum^*|||w|| \ge 2 \}$ $ii. C = \{w \in ...
2
votes
0answers
43 views

Maths, esp. Godel, and poetry

At the risk of being an interloper: I'm a poet with a bit of mathematical training. Right now I've got a grant from the Arts Council of Northern Ireland to write a collection (loosely) based on the ...
0
votes
1answer
23 views

Are there known patterns among minimal expressions?

Let $R = F[z_1, z_2, \dots]$ be the finite-degree polynomials in a countable number of variables. Let $\mathcal{E}(R)$ be the set of all expressions of polynomials. Note that there could be an ...
0
votes
1answer
17 views

not understanding the part of the answer for drawn turing machine

Could someone please tell me what does capital B mean here ? of course I know R and L stands for right and left... and also I know for example if we have a,b,R (which tells you if you have an a , ...
0
votes
0answers
45 views

My notes on $\Bbb{Z}/p\Bbb{Z}$-theoretic computational complexity

(Question at the very bottom) Def 1. Let $F = \Bbb{Z}_p$ be a finite field. Then an $F^k$-machine is a machine with $k$ input / output memory slots. All computations are done in the field $F$ and ...
2
votes
2answers
41 views

Regular Expressions Help [duplicate]

I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ...
0
votes
1answer
67 views

how to a draw a turing machine that has the same number of a's ,b's and c's

how to a draw a turing machine that has the same number of a's ,b's and c's SOMELANGUAGE = {abc acb bac bca cab cba aabbcc aabcbc}
0
votes
1answer
56 views

Reflexivity of the relation between strings over language $L$ defined by $xc \equiv L$ and $yc \equiv L $

Given any two strings, call them $x$ and $y$, over any language $L$ and given property such that if $xc \equiv L$ and $yc \equiv L $ (where $c$ is some string), then $x \equiv y$. I would ...
0
votes
2answers
36 views

DFA Construction with three strings in language

Draw DFA that recognizes the following language, with the alphabet {0, 1} {0011, 11, 0101} I'm having a lot of trouble with this, because I know DFA have to have a determined path from each state ...
-1
votes
1answer
51 views

Finding the CFG (Context Free Grammar) of a language

Can we write a CFG (Context Free Grammar) for the set of all non-empty string whose length are multiple of 3 on the alphabet $ \Sigma = \{A,R,G,C\} $
1
vote
1answer
40 views

Constructing PDA for a language

I want to prove or disprove that for a given two PDA's (Pushdown Automata) $M_1$ and $M_2$, we can build a PDA $M$ such that $$L(M) = \{w \in L(M_1) \mid w\text{ contains some string in ...
0
votes
0answers
27 views

Show L is not context free using the CFL pumping lemma

I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$ So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = ...
8
votes
4answers
592 views

Why isn't there a pumping lemma for recursively enumerable languages?

I'm studying the theory of computation, and I know there are pumping lemmas for regular and context-free languages, but why not for recursively enumerable languages? Is there something about a Turing ...
1
vote
0answers
51 views

If $P=NP$, prove that $L' \in NP$

I think I'm overthinking this problem and need some hints in the right direction. The goal of this question is to show that if $P=NP$ then for every language $L \in NP$ via a polynomial time verifier ...
0
votes
0answers
22 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
0
votes
1answer
29 views

Are these statements concerning formal languages true or false, and why?

Please answer the following question and give me the reasoning. Are the following statements true or false? If a statement is false, give a counterexample. $uv=vu$ for all strings $u ≠ λ$ and $v ≠ ...
0
votes
1answer
33 views

Prove a language is Context Free

I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of $a$'s and $b$'s with an equal number of $a$'s and ...
2
votes
1answer
66 views

Prove 2-HamiltonianCycle $\in \textbf{NP}$

Just want to verify that I have the right idea here with this hamiltonian cycle question. $HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex ...
2
votes
0answers
65 views

Determine the language that corresponds to the following automata.

I want to determine that language that corresponds to the following automata Note: $q_{6}$ have arrow to $a$ to himself. I started with the minimal words: $aaabb$ $aaba$ $aaaba$ $bababa$ the ...
0
votes
0answers
15 views

What is the correct notation for A∆B?

For the alphabet Σ = {0, 1}, let A, B, C ⊆ Σ∗ be the languages below. i. A={1,0,00,11,000,111,0000,1111} ii. B={w∈Σ∗|||w||≥2} iii. C = {w ∈ Σ∗|||w|| ≤ 2} Note: ||w|| denotes the length of the word ...
0
votes
1answer
42 views

Determine the following languages of Σ∗

For the alphabet Σ = {0, 1}, let A, B, C ⊆ Σ∗ be the languages below. i. A={1,0,00,11,000,111,0000,1111} ii. B={w∈Σ∗|||w||≥2} iii. C = {w ∈ Σ∗|||w|| ≤ 2} Note: ||w|| denotes the length of the ...
1
vote
1answer
33 views

There is a sequence of operations on grammars of a string that strictly decreases the size of grammars down to the smallest grammer.

I'm trying to figure out the smallest grammar problem, which yes I know is impossible since it's such a hard problem, but humor me for a sec. Let $g$ be a smallest grammar for the string $s$ over the ...
1
vote
1answer
39 views

Name for grammars with rules $A \to uA$

Recall that a right-linear grammar is a grammar that consists of rules of the form $A\to uB$, where $A$ and $B$ are non-terminals and $u$ is a (possibly empty) word of terminals. Similarly for ...
1
vote
1answer
136 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
0answers
21 views

Eliminate Useless Productions

How do I eliminate useless productions from the grammar: $S \rightarrow a|aA|aaB|abC$ $A \rightarrow aB|\lambda$ $B \rightarrow Aa$ $C \rightarrow cCD$ $D \rightarrow ddd|aC$
1
vote
1answer
65 views

Prove or disprove whether the following is a regular language

I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ...
0
votes
1answer
18 views

Eliminating Unit Productions

Eliminate all unit-productions from the grammar: $S \rightarrow abA\:|\:A\:|\:B$ $A \rightarrow B\:|\:ba\:|\:aBA$ $B \rightarrow A\:|\:aa\:|\:aA$ An article I was reading said that a unit ...
1
vote
3answers
55 views

Prove that this language is not regular (Pumping Lemma)

Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$
1
vote
1answer
50 views

Is the language $L=\{ww^f|w\in \{0,1\}^*\}$ CFL?

Where $w^f=$flipping the bits of w. For example, $(0010)^f=1101$, $(010111)^f=101000$ I tried to prove that $L$ is not CFL using the pumping lemma, with no succeed. In addition, I need to prove ...
0
votes
1answer
25 views

Finding a length of a set?

Let $\Sigma=\{a,b,c\}$ and let $\Sigma^*$ be the set of all words $w$ using letters from $\Sigma$. Define $$L(w)=\text{length}(w)$$ for all $w\in\Sigma^*$. How to calculate the L(w) for the words ...
0
votes
1answer
32 views

Prove L is not a regular language (A Finite State Automaton cannot accept it)

$$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ...
1
vote
2answers
66 views

How to solve pumping lemma questions?

I am trying to prove that L = { aNbMaN-M|N>=M>=0} is not regular using the pumping lemma. I am pretty confused how to solve this. What I have so far (which I am not sure is right) is: Assume L is ...
1
vote
1answer
388 views

Build a deterministic turing machine to decide L = { ww }

As the title says. w is in {a, b}^*.Note that I am not looking for the non-deterministic one. Use a Turing machine of one tape and "pointer". An idea: I thought that I would do something like ...
1
vote
1answer
34 views

Recursively Enumerable Languages and Turing Machines

L1 = { M | Turing Machine M terminates for at least 637 inputs} L2 = { M | Turing Machine M terminates for at most 636 inputs} One of them is recursively enumerable, which one?
0
votes
0answers
33 views

LL(1) grammar for boolean language

Is there a LL(1) grammar for this language? Here are some words of this language. It is a boolean logic, which uses negation, binary operators and braces (redundant braces are allowed too): A ...
0
votes
1answer
57 views

Accepting/rejecting states in Turing Machine

In language decidability problems, a TM halts with a halting state, an accepting state or a rejecting state. My understanding is that when a TM machines halts on accepting state, it removes everything ...
1
vote
1answer
45 views

Checking some Regular Expression problems

I'm given the alphabet $$ \Sigma = {\{a,b}\} $$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ...
1
vote
1answer
21 views

How to prove the following related with regular languages

How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ?
1
vote
0answers
58 views

Prove the following by using mathematical induction

If we define the alphabet such that $$ \Sigma = {\{a,b}\} $$ and let $w$ be a string over it. I'd like to prove $$ ( \operatorname{comp}(w))^R = \operatorname{comp}(w^R) $$ where $$ w^R$$ and ...
0
votes
1answer
53 views

Pure Lambda Calculus: Call-by-value Free Variable Argument Application Reduction

In pure lambda calculus, under the call-by-value reduction strategy, a term of the form $(\lambda x. x)y \rightarrow y$ implies that the free variable $y$ is a value. However, only abstractions are ...
0
votes
1answer
40 views

Palindromes with 2 symbols and $3|l(u)$

The following grammar generates palindromes with 2 symbols. $$G=\{\{S\}, \{a,b\}, \{S\rightarrow\epsilon|a|b|aa|bb|aSa|bSb\}, S\}$$ So if I'm right, each $u$ in the language $L$ generated by $G$ is a ...
1
vote
1answer
56 views

Question on Proof that the Fibonacci Word is Sturmian

I am currently reading a text where it is proved that the infinite Fibonacci Word $u$ defined as the limit of the sequence $$ u_n = \varphi^n(0) $$ where the morphism is given by $\varphi(0) = 01, ...
1
vote
2answers
38 views

Prove by induction on a string

I want to practice proving the following: Given a binary string s, I want to prove $s$ has the same number of substrings 01 and 10 $\iff$ the first and last character of $s$ is the same. For ...
2
votes
0answers
27 views

Recursive and Recusively enumerable

{1^n | n finite integer and >1}, is this language recursive? I'm not sure how to prove that a language is recursive, I only know that there should be a TM that accepts any finite input and then ...
0
votes
1answer
73 views

find a regular expression and FA that each define L1 ∩ L2

from the following pairs I am trying to find a regular expression and FA that each define ...
0
votes
1answer
22 views

How can I show ithat a language is regular?

I have a very quick question about regular languages, I think $\{a^{2n}| n\geq 1\}$ is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ...
0
votes
1answer
28 views

Question About Pumping Lemma used on a FA

I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ...
1
vote
1answer
54 views

Prove $L$ = $\{\langle M \rangle$ | $M$ is a TM over $\{0,1\}$ and $\langle M \rangle \langle M \rangle \notin \mathcal{L}(M)\}$ is undecidable.

Was stuck on this for a bit so I need to know if I am on the right track. To show that $L$ is undecidable we will show that $\overline{L}$ is undecidable instead. Suppose $\overline{L}$ is decidable ...