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
18 views

State Change in a Turing Machine(Computer of Integer Function)

Im trying to learn how TM can be used as a computer of integer functions. I have this problem The text books gives the construction as follows I understand that intially the R/W head will be ...
0
votes
2answers
30 views

What is the language of following CFG?

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. $$S → aS \mid A \\ A → aAb \mid bAa \mid \epsilon$$ Which of the following ...
1
vote
1answer
32 views

How we derive language from grammar by bottom up or any other approach?

Consider a CFG with the following productions. S → AA | B A → 0A | A0 | 1 B → 0B00 | 1 $S$ is the start symbol, $A$ and $B$ are non-terminals and $0$ and $1$ are ...
1
vote
1answer
28 views

proving that if a FFA accepts L=> L is a regular language

Ok, so after wasted time for nothing on this question that I asked yesterday: proving that a regular language can be accepted by a fast finite automaton Now comes the more interesting prove: ...
0
votes
1answer
76 views

Defining an equality

When we define an equality ($=$) of things, for example of vectors in $\mathbb{R}^n$ or of sets in ZF by the Axiom of Extensionality, are there properties that we need to check in order for $=$ to be ...
0
votes
1answer
33 views

proving that a regular language can be accepted by a fast finite automaton

Let it be L a regular language. Prove that exists a fast finite automaton (FFA) M which excepts L. Definition of FFA: FFA is a 6-tuple M=$<Q,Σ,P,δ,s,A>$ which: 1. Q is a finite set of ...
4
votes
2answers
48 views

proving that $L_\text{almost}$ is a regular language

Let it be L, a regular language. we will define: $L_\text{almost} = \{ w'\mid \exists w\in L\ w' \text{ is almost similar to }w \}$ a word $w'$ is almost similar to $w$ if they are in the same ...
0
votes
0answers
23 views

Prove that the set of palindromes are not regular languages

Let L = {w| w ∈ {a,b,c} * is palindrome} Could someone explain me how to prove that L is not regular, because all answers I've found are done with 2 symbols(a,b), and I'd need to prove it with 3.
3
votes
0answers
61 views

Positive existential theory of an extension of the ring

When we know that the positive existential theory of a ring $R[x]$ in a language $L$ is undecidable, does it follow that the positive existential theory of $R[x,y]$ in the same language $L$ is also ...
0
votes
1answer
27 views

DCFL are closed under Intersection with Regular Languages?

Let $L_1$ be a regular language, $L_2$ be a deterministic context-free language and $L_3$ a recursively enumerable, but not recursive, language. Which one of the following statements is false? $L_1 ...
0
votes
1answer
24 views

$L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular?

Given language : $L=\left\{ s \in (0+1)^* \mid \text{ for every prefix s' of s,} \mid n_{0}(s')-n_{1}(s') \mid \leq 2 \right \}$ is regular? Somewhere it explained as : Here we need just 6 states ...
2
votes
1answer
180 views

Construct a deterministic Turing machine that decides the language $L=\{w\in\{a, b\}\mid w\text{ contains an occurrence of }ab\}$

So we are asked to construct a deterministic Turing machine. I have constructed a Turing machine, but I'm not sure if it's correct. Here is my Turing machine: For the question above, I'm just ...
0
votes
0answers
39 views

Proof That Undefined Notions Exist

Undefined notions are terms which are to be understood intuitively, without precise definition. What's the proof of them being needed? I get that when we try to define a thing we need to use terms, ...
1
vote
2answers
34 views

String in an kleene star alphabet

Let Σ = {a, b}. How many strings of length 10 are in the language (bb + aab)*? If this a matter of writing them out or is there a formula to it?
1
vote
0answers
22 views

why is automaton with a queue is more powerful than an automaton with a stack?

what is the logic behind this statement that with the use of queue the automaton becomes more powerful , is it that in a queue , we may do operations from both the ends as compared to a stack so it is ...
1
vote
0answers
8 views

Hasse diagram of $\operatorname{LL}(k)$, $\operatorname{LR}(k)$ language sets

I'm trying to establish (through constructing a Hasse diagram) the subset relationship between the classes of languages that can be parsed by $\operatorname{LL}(k)$ and $\operatorname{LR}(k)$ parsers. ...
0
votes
0answers
39 views

Prove that $L = \{0^n1^m \mid n ≥ 10, m ≤ 50\}$ is regular and that any subset of it is regular

Question: Let L = {0n1m, n ≥ 10 m ≤ 50}. Prove that this is a regular language and that any subset of it is also regular. Answer or approach: 0 is regular, 1 is regular since any symbol in ∑ is ...
2
votes
0answers
50 views

Regular expression for string's of a's and b's beginning with b and not having two consecutive a's

Question: Write a regular expression for the following language: "All strings of a's and b's in ∑* beginning with b and not having two consecutive a's. A textbook says the answer is (b+ba)*. ...
1
vote
2answers
40 views

Prove that $\{w \mid \text{ w has even length and the first half of w has more 0s than the second half of w} \}$ is not regular?

I have had some difficulties understanding proofs that a language is not regular using the Pumping Lemma, and now I need to prove that the following language $$A = \{w \mid \text{ w has even length ...
0
votes
1answer
16 views

Algorithm for Regular Language

Let $L$ be a regular language with the alphabet $\Sigma$. I'm trying to find an algorithm to tell whether $L=\Sigma^{*}$, whether $L$ accepts all strings in its alphabet. I think this algorithm uses ...
16
votes
6answers
847 views

About the position of “for all” quantifier

I'm not expert in logic, but as far as I know, quantifiers comes before the predicates they refer to. Still, if written in english, there are statements which sounds better when you don't put all the ...
1
vote
1answer
21 views

CFG for this language

Give a CFG for the language $\{x \in \{a,b\}^* | x \not= ww \text{ for some w} \in \{a,b\}^*$ In my attempt to do this I understand odd length strings are automatically in the language, but don't ...
0
votes
2answers
19 views

Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1=\{a^mb^mca^nb^m∣m,n≥0\}$ $L_2=\{a^ib^jc^k∣i,j,k≥0\}$ Then $L$ is Not recursive Regular Context free but not regular ...
0
votes
0answers
31 views

Converting CNF to GNF

Considering the CNF grammar below, I need to convert it to GNF using the equations in a semiring method and Order the equations in the the natural order. However, I Do not have to convert the ...
0
votes
1answer
27 views

Converting Grammar to CNF

So I have to convert the following grammar to CNF. However in order for me to do so, I know I will have to first: ...
0
votes
0answers
20 views

Solving the corresponding semiring equations to derive a rational expression for L( G)

Let say we have the following grammar G: S -> bA -> aB -> 1 A -> aA -> bB B -> bA -> aB -> 1 How would i go about solving the ...
0
votes
2answers
20 views

Find two non-empty languages whose concatenation is equal to another language

Let $L=\{a,b,ab,ba,bb,aab,bab,baab\}$. Find two Languages $L_1$ and $L_2$, both not equal to $\{\lambda\}$ over the Alphabet $\{a,b\}$ such that $$L_1\cdot L_2=L.$$ The solution is $L_1=\{a,b,ba\}$, ...
2
votes
1answer
18 views

Given a language $L_1$ over the $\Sigma$ alphabet, is the following statement correct?

Given a language $L_1$ over $\Sigma$ alphabet, is $L_1L_1^*L_1=L_1^*L_1^2\cap L_1^2\Sigma^*$ Correct? I started by simplifing the expression to : $L_1^*= L_1^*\cap L_1^2\Sigma^*$ Now, my problem was ...
0
votes
0answers
20 views

Chomsky Normal Form CFG for a language

We define the language L inductively as follows: ε ∈ L, if x ∈ L then so are (x) and [x], if x and y are both in L then so is xy. I'm trying to write a Chomsky Normal Form CFG for this language. I ...
0
votes
1answer
167 views

Minimum Pumping Length

What is the minimum pumping length of (01)* The solutions says 1, but can someone explain why that is? I understand this language accepts the empty string, but the minimum pumping length cannot be 0. ...
0
votes
0answers
16 views

Are languages made by splitting regular lanaguage regular?

Let's have language $L$: $L = \{u·v, u ∈ L_1, v \in L_2\}$ Lanaguage $L$ consists of words from $L_1·L_2$. We know that $L$ is regular language. In other words languages $L_1$ and $L_2$ are made by ...
0
votes
0answers
24 views

Syntax in Robert Harper's book

I'm trying to read Practical Foundations For Programming Languages by Robert Harper, especially I'm interested in existential types. So I started with this introduction: In the beginning I was ...
1
vote
3answers
53 views

Closure property of regular language

I am trying to prove the closure property of regular language with a function $f(w)$ over alphabet $\Sigma$ for any string $w \in \Sigma^*$. $f(w) =$ string obtained by taking symbols of $w$ at even ...
1
vote
1answer
76 views

How to draw DPDA for language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\} ?$

An exercise problem $:$ Give a deterministic PDA for the language $L = \{a^ncb^{2n} | n \geq1\}$over the alphabet $\Sigma =\{a,b,c\}$.Specify the acceptance state. My attempt $:$ Grammar of given ...
0
votes
1answer
28 views

Context free grammar for these langauges?

I've been working on trying to generate context free grammars for different problems and currently I'm working on these but after trying over and over, I can't come up with ones for these: 1) the ...
0
votes
0answers
18 views

Closure property of regular languages

I am trying to understand the closure property of regular languages. I am defining two functions func1(w) and func2(w) over alphabet Σ for any string w ∈ Σ∗. func1(w) gets the string of symbols of w ...
0
votes
1answer
25 views

Show there is a string that's length is less than or equal to the number of states in an NFA

I'm trying to prove that this is true but cannot find a good way to show this proof. The question is below: Let $T$ be an NFA such that the language defined by $T$ is neither empty nor $\Sigma^*$. ...
0
votes
0answers
14 views

Suppose that CFG G defines $T^*$. Does G defines every language $L$ over the alphabet T?

Suppose that CFG G defines $T^*$. Does G defines every language $L$ over the alphabet T ? Why the answer for this question is false ? G generates every string in the set $T^*$ and if $L$ is a ...
-1
votes
1answer
13 views

Newbie Question formal languages N-1 for a language typ 3

I have the following problem: If I have a Grammar G with (Vn, Vt, P, S) Vn ={S}, Vt = {0} P: S -> 0S S -> 0 Why is the derivation from G: 0^(n-1)S? S => 0S => 00S => ... => 0^(n-1)S => 0^n Is it ...
0
votes
1answer
51 views

How to determine if a word in $\Sigma^*$ is in a language?

I'm currently doing work on discrete mathematics in my free time and am having some difficulties with understanding some questions pertaining to Languages defined by regular expressions. To be ...
0
votes
0answers
30 views

What does it mean “the transition function of FA M is derivable in CFG G”?

I don't understand this question. Let $M$ be a finite automaton. If every production of G is accepted by M and the transition function of $m$ is derivable in G, then $L(G)$ = $L(M) ?$ What does ...
0
votes
1answer
21 views

Need help understanding question about how many languages can fit set?

I've been viewing the Coursera videos on finite autamata and need some help understanding a question. What’s the number of non-empty languages that contain only strings of 0's and 1's of length ...
1
vote
1answer
25 views

Using Pushdown Automata to prove a language is context free

How do I prove that the language L is a context free using Pushdown Automata? I would like to know the process of proving it. I am still new to CFLs and PDAs.
0
votes
2answers
131 views

Give a regular expression that generates C.

Question: In certain programming languages, comments appear between delimiters such as /# and #/. Let C be the language of all valid delimited comment strings. A member of C must begin with /# and ...
0
votes
1answer
42 views

difference between a string and alphabet symbols

What's the difference between a string and a symbol in the alphabet for an automata? For example if you have an alphabet $\Sigma={0,1}$ Is a string a particular combination (set?) of alphabet ...
0
votes
1answer
24 views

Unicity of functions and their infinite expressions.

While studying boolean algebra (where the lattice is over A={0,1}) I realized that I can have the set of all the functions from A × A × ... × A to A, the set A^(A×...×A). This set is finite, however i ...
0
votes
0answers
27 views

Constructing a push down automaton

I'm having trouble constructing a PDA for the following language: $$L=\{x\#y\#z\mid x,y,z\in\{a,b\}^+\text{ with }x\approx y\text{ or }x\approx z\text{ or }y\approx z\}$$ Define $x\approx y$ as ...
0
votes
2answers
26 views

Creating DFA to prove closure properties

I am given a language $L \subseteq \Sigma^*$ and symbol $a \in \Sigma$. Let $a/L= \{ w \in \Sigma^*~|~ wa \in L \}$ ex. String that end in $a$ but with that last $a$ removed. I am trying to prove that ...
2
votes
1answer
26 views

Is this language semidecidable?

I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following . If $L_1$ ...
2
votes
3answers
89 views

Create a formal regular expressions that accepts all strings of 1 and 0 that do not contain 101

I'm working through a textbook on automata theory and I'm stuck on this regular expression problem. Create a regular expression for the following language: The set of all strings that do not contain ...