Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

2
votes
2answers
44 views

Intersection/Union of recursively enumerable languages that aren't decidable?

For $L_1, L_2 $ and $L_1 \in RE $ and $ L_1\notin R$ and $L_2 \in RE $ and $ L_2\notin R$ I was asked to prove/disprove if the following can occur: $L_1 \cap L_2 \in R$ $L_1 \cup L_2 \in R$ $L_1 ...
2
votes
1answer
36 views

Neural network: noisy temporal sequence converter (transducer?producer?) on demand?

I start to suspect this problem is very hard now that I cannot find a single relevant literature on the subject, but it's too late to change the class project topics now, so I hope any pointers to a ...
9
votes
3answers
636 views

Why use languages in Complexity theory

I'm just starting to get into the theory of computation, which studies what can be computed, how quickly, using how much memory and with which computational model. I have a pretty basic question, but ...
5
votes
3answers
412 views

Is it compulsory that every infinite set be non regular?

I am confused regarding the statements provided by one of our faculty regarding "Is it compulsory that every infinite set is non regular though every finite set is a regular set". Providing ...
3
votes
1answer
34 views

Regular expressions and semi-linear sets

In proving Parikh's Theorem, my Theory of Computer Science textbook defines a linear set as: $u_0 + \langle u_1, \dots, u_m \rangle = \{u_0 + a_1u_1 + \dots + a_mu_m \mid a_1, \dots, a_m \in ...
6
votes
3answers
194 views

I need clarification about DFA's and DFA acceptable languages

In class yesterday we went over DFA's and DFA acceptable languages. An example of a language that is not DFA acceptable was given as $\{ ab, aabb, aaabbb, aaaabbbb, \ldots \}$. The reason given was ...
1
vote
1answer
38 views

How to check ambiguity of a specific grammar

Giving the following Grammar: S → ^ | SaSMSM | SMSaSM | SMSMSa M → b | c ^ means eopsilon. How can i check whether its ambgious or not? My intuition is ...
0
votes
2answers
47 views

Find a CFG for a language

In an assignment I've been asked to find a CFG for $a^x b^y a^z b^w$, where, $x,y,z,w \in \mathbb{N}^+$, $y > x$, $z > w$, and $x+z = y+w$. A hint was given, think of the language as $(a^p ...
2
votes
3answers
157 views

Does there exist a proof of closure of regular languages under regular substitution by giving the corresponding DFA?

Every proof I can find of this result is by way of regular expressions. Is there any "constructive" proof that defines the corresponding DFA (probably NFA)? For instance the proof of concatenation ...
3
votes
2answers
215 views

Proving that a word is *not* generated by a context-free grammar

I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF... How did they get the answer so that ab ...
2
votes
0answers
54 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
3
votes
3answers
72 views

Compression of non-adjacent structure using grammar

I'm working with compression algorithms that use context-free grammars (e.g. RE-PAIR and SEQUITUR). These grammars look for frequently occurring digrams (pairs of adjacent symbols) in an input string ...
0
votes
1answer
21 views

Canonical infinitely ambiguous languages

In an article I am currently reading the grammar S → SS | a | ε is being described as canonical infinitely ambiguous. The infinitely ambiguous part I have no problem recognizing, but does ...
3
votes
1answer
40 views

“Grammar inference” for 2-D images

Others have studied the following question: given a set of words $w_1,w_2,\dots \in \Sigma^*$, find a regular grammar (or a context-free grammar) that generates all of those words, is "natural" in ...
0
votes
1answer
42 views

a regular language so that $unary(L) \notin $Context Free Languages [closed]

I need a regular language $ L\subseteq \{0,1\}^{*} $ so that $unary(L)$ is not context free. unary of $L$ is defined by: $$unary(L) = \{0^{1x} : x \in L \}$$ Example $L = \{0, 11\} $ $\rightarrow ...
3
votes
1answer
109 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
3
votes
1answer
32 views

grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?)

Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are ...
0
votes
3answers
141 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
0answers
33 views

A construction to show a very restricted substitution closure result for DCFLs

Let $P$ be a deterministic PDA recognizing a deterministic CFL with a binary alphabet. Modify $P$ to identify its reading states (denote this subset of states by $R$) in accordance with the ...
0
votes
2answers
53 views

The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language $$ L = \{ \langle M \rangle | \text{$M$ is a TM and $M$ accepts some string $w$ which has ...
-2
votes
1answer
67 views

Is the language $\{ a^pb^q \mid p, q \text{ are prime} \}$ regular? [closed]

I am interested to know whether that language $$ L = \{ a^pb^q \mid p, q \text{ are prime} \} $$ is regular. How do you prove that it is not regular?
0
votes
1answer
34 views

Turing machines and languages — recursive (enumerable) or not

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could ...
10
votes
4answers
492 views

Regular language not accepted by DFA having at most three states

Describe a regular language that cannot be accepted by any DFA that has only three states. I'm not really sure where to start on this and was wondering if someone could give me some tips or ...
2
votes
1answer
52 views

Proving that the continuation of a non-regular language is not ω-regular

I want to prove that a language is not $\omega$-regular. The language I'm working with can be defined as: $$L = \{ a_1 \dots a_n x^\omega ~ | ~ n > 0, a_1 \dots a_n \in L^\prime \}$$ where ...
1
vote
1answer
29 views

Proof that $A_{DFA}$ is decidable in Sipser

It seems like the proof that $A_{DFA}$ is decidable in Sipser (2nd ed.) assumes the computation will halt... and hence only really proves that $A_{DFA}$ is recognizable. The language $A_{DFA}$ is ...
1
vote
2answers
86 views

proving that if $\{w\$w^R | w \in L\}$ is context-free then $L$ is regular [closed]

I am trying to prove this following theorem, can someone help please? Let $L$ be a language over the alphabet $\Sigma = \{ a,b \}$. If $L' = \{ w\$w^R \mid w \in L\}$ is context-free, then $L$ is ...
1
vote
2answers
96 views

Find a context-free grammar for the language $L=\{a^nb^m\mid 2n<m<3n\}$ [closed]

I need to find a context-free grammar for the following language which uses the alphabet $\{a, b\}$ $$L=\{a^nb^m\mid 2n<m<3n\}$$
6
votes
3answers
134 views

Demonstrate that DPDA is closed under complement by construction

I've been trying for quite some extended time to find a construction so that I can formally demonstrate that a deterministic PDA is closed under complementation. However, it happens that every idea I ...
-1
votes
1answer
29 views

Left recursion for LL(1) [closed]

Hi I am trying to solve a LL(1) form question for first n follow rule The question is A::=BC|C B::=Bd|ef C::=gh|j What I have done to eliminate left recursion ...
-2
votes
2answers
323 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
3
votes
1answer
51 views

Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages

I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages. I know ...
5
votes
2answers
53 views

Intersection of two NPDAs

Is there a way to take the interection of two NPDAs? I can't seem to find anything that can make that happen, but it seems like the type of thing that is should be relatively trival.
1
vote
0answers
56 views

Complexity of Languages [closed]

1) Find language $L_1 \subseteq L_2 \subseteq L_3$ such that both $L_1$ and $L_3$ are not context-free languages, but $L_2$ is a regular language. 2) Find language $L_1 \subseteq L_2 \subseteq L_3$ ...
2
votes
0answers
56 views

If $L_1$ is regular and $L_1 \cap L_2$ context-free, is $L_2$ always context-free? [closed]

If $L_1$ is a regular language and $L_1 \cap L_2$ is a context-free language, does it mean that $L_2$ is a context-free language too? I attempted to prove that $L_2$ was not required to be ...
0
votes
2answers
124 views

TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5

I am trying to describe a TM that decides the language $A=\{0^{5^n} \mid n\ge0\}$. I know how to do this for $0^{2^n}$, marking off every other 0 in each pass. In my case would it work marking off ...
0
votes
2answers
63 views

Generating all strings that a regular expressions describe

I'm having trouble generating the set of strings, which a regular expressions describe. A typical regular expression can look like this: ...
24
votes
4answers
14k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
3
votes
1answer
104 views

Prove that context free languages aren't closed under DropMiddle

The question is simple: $\qquad \operatorname{DropMiddle}(L)=\{xy\in\Sigma^* \mid |x|=|y| \land \exists a\in\Sigma\colon xay\in L\}$. Prove that CFL's aren't closed under ...
0
votes
2answers
62 views

Proving that context-free languages are closed under inserting symbols [closed]

This is a theoretical computer science question, regarding the proof of whether or not context-free languages are closed under an operation. This means basically that any context-free language which ...
2
votes
1answer
47 views

Is $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ context free?

I was wondering if this language is context-free: $L = \{ x \in \{ 0, 1 \}^* : |x| = 2^n $ for some natural number n $\}$ I know that this language is not regular because it fails the pumping lemma ...
0
votes
1answer
24 views

Construct context free grammar from language

I have been starting to learn about CFGs and PDAs and have gotten familiar with the simple stuff. I have been able to construct CFGs for simple languages but this question is more specific: $\lbrace ...
1
vote
0answers
44 views

Designing a different grammer that generates same expression [duplicate]

I've a set of grammar rules like this: $$ \begin{align*} &S \to AbB \\ &A \to aA|\epsilon \\ &B \to aB|bB|\epsilon \end{align*} $$ The grammar generates the following words: $$ ...
2
votes
1answer
123 views

Is L= $\{ww \mid w \in \{a,b\}^*\}$ context-free? [closed]

Let $L = \{ww \mid w \in \{a,b\}^*\}$. In other words, each word of $L$ is some string repeated twice (some string concatenated with itself). Is the language $L$ context-free?
0
votes
1answer
47 views

If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? [closed]

If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free? I am aware that if $L_1$ and $L_2$ are context free languages then the ...
2
votes
1answer
50 views

Limits to the definition of a language

Is there any limit to what we can define as a language? Is any set of symbols a language? For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$? ...
3
votes
2answers
79 views

Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$ [duplicate]

I have a language where each string in the language has even amount of $0$'s as $1$'s (e.g., $0101$, $1010$, $1100$, $0011$, $10$ are all in the language). I was hoping to define a context-free ...
4
votes
2answers
466 views

Sandwiching Languages

I am studying for my algorithms final and came across the following problem: Find three languages $L_1 \subset L_2 \subset L_3$ over the same alphabet such that $L_2 \in P$ and $L_1,L_3$ are ...
1
vote
1answer
35 views

Proving a language is not a regular language but a context free language [duplicate]

I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$. I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is ...
2
votes
1answer
46 views

Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $ \Omega (\log\log n) $ space complexity. I'm looking for an example of a language which is $ \Theta (\log\log n) $ space complexity ...
-1
votes
1answer
70 views

Kleene Star Property : L*L* = L* [closed]

I am trying to prove this expression but don't have an exact idea about what to do: If $E$ is any alphabet and $L$ is any language $L \subseteq E^*$. Prove that $L^*L^* = L^*$.