Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

0
votes
2answers
39 views

Converting to CFG from a CFL? [duplicate]

I am trying to learn CFG. Now to make a CFG from a CFL it is really difficult for me. Is there any simple rule or steps so that I can easily find a CFG for a CFL. I am trying to solve one problem ...
0
votes
0answers
18 views

Designing CFG for sequences of words of which two arbitrary ones are reversals

Let $L$ = {$x_1\#x_2\#...\#x_k$ : $k\;\ge\;1$, each $x_i\;\in\;\{0,1\}^*$ and $\exists i,j$ such that $i < j$ and $x_i$ = $x^R_J$}. For example, $001001\#0010\#100100\#00001$ is in $L$ because ...
0
votes
1answer
58 views

Regular expression for a binary number that includes “10” and has an odd number of 0's

I have been struggling trying to write a regular expression for a binary number that includes "10" and has an odd number of 0's, so far I have (1) * (00) * 10(1010) * (00) * (1) * but it doesn't ...
3
votes
1answer
67 views

Question regarding Cook-Levin theorem proof

I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing ...
1
vote
1answer
33 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
1
vote
1answer
50 views

How to prove that this is NP complete?

I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete. I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete ...
3
votes
1answer
60 views

How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$. Is it possible to convert $G$ into an unambiguous grammar which also generates $L$? If ...
2
votes
1answer
35 views

What is one method used to prove each palindrome is in its own Myhill-Nerode equivalence class?

I understand how you can use a contradiction in regard to a DPDA to show a language has finitely many Myhill-Nerode equivalence classes, but what is the method used to show each string of a language ...
2
votes
1answer
89 views

Flowcharts vs DFA resp FSM equivalency

First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I ...
2
votes
1answer
70 views

Turing recognizable & decidable: binary strings with even length. Let A = {(M) | M is a DFA such that L(M) is not the same as EVEN}

Having trouble with this homework problem. In order to show that A is Turing recognizable and decidable. $\text{EVEN} = \text{binary strings with even length}$ $Let\;A = \{(M) | \,M\; \text{is a DFA ...
1
vote
1answer
37 views

Applying the context-free pumping lemma to a language with crossed nestings

For proving language $\{a^nb^mc^nd^m \mid n,m > 0\}$ is not context free. Do I have to use $z = a^pb^pc^pd^p$ as pumping lemma string where $p$ is pumping length? Or do I have to use a string that ...
-2
votes
0answers
32 views

Why is $L_1-L_2$ regular for any two regular $L_1,L_2$? [closed]

How do I show that for any two regular languages $L_1,L_2$, their difference $L_1 - L_2$ is also regular? I tried to solve this but I'm not sure my solution works.
-1
votes
1answer
37 views

Prove a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
-4
votes
1answer
43 views

Show whether the language with almost as many 0 as 1 in every prefix is regular [closed]

This is the exercise: Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at ...
1
vote
5answers
677 views

Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ ...
1
vote
2answers
40 views

Is $a^n b^n c^n$ context-free? [duplicate]

I am new to grammars and I want to learn context free grammars which are the base of programming languages. After solving some problems, I encountered the language $$\{a^nb^nc^n\mid n\geq 1\}\,.$$ ...
5
votes
3answers
90 views

Prove that the complements of pumping-style languages are context-free

Define $L = L(u,v,x,y,z) = \{uv^ixy^iz : i \geq 0\}$, with $u,v,x,y,z \in \Sigma^*$. Prove that $\overline{L}$ is a CFL for all $u, v, x, y, z$ Clearly, $L$ is a CFL, as it is generated by the ...
1
vote
1answer
38 views

Example of a superword w such that v^2 isn't its subword

What is an example of an infinite word(superword) w such that if a nonempty word v belongs to L = {1,2,3}*, v^2 isn't a subword of w? For example if w = 123123123...123 and v = 123, v^2 = 123123 ...
4
votes
1answer
105 views

Show that every grammar for an inherently ambiguous CFL has infinitely many ambiguities

Prove that if a CFL $L$ is inherently ambiguous, then for any grammar $G$ with $L(G) = L$, there are infinitely many strings in $L$ that have (at least) 2 different derivations in $G$. Here's a ...
4
votes
2answers
175 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
2
votes
2answers
35 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
0
votes
2answers
78 views

Can we prove that all CFLs can be recognized by a Turing Machine in polynomial time?

This question came up while a group of students at my school were studying for our qualifying exams. The question on an old exam was, Consider the following six classes of languages: Context free ...
2
votes
3answers
96 views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
2
votes
1answer
229 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
43
votes
5answers
11k views

How to prove that a language is not context-free?

We learned about the class of context-free languages $\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is ...
3
votes
1answer
42 views

Creating a CFG that connects lengths of three blocks

I have to create a CFG which generates $$\{a^n (ab)^n c^m d^\ell e^k \mid n>0, k, \ell, m\ge0, k<m, m=\ell+k\}$$ The first part is easy enough, I came up with $$\begin{align*} S &\to ...
3
votes
1answer
45 views

The language of any constant-time Turing machine is regular

Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular. This seems to be a ...
0
votes
1answer
45 views

When using the Pumping lemma, how do I deal with different cases of y?

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$ I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know ...
-2
votes
0answers
36 views

Is the Language of all x#y so that x is not a subword of y context-free? [duplicate]

I am considering the language $L = \{x\#y \mid x, y \in \Sigma \text{ and } x \text{ is not a subword of } y\}$, where $\Sigma = \{a,b\}$ and $\#$ is a symbol not in $\Sigma$. I wish to determine ...
2
votes
2answers
350 views

Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$

Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.
1
vote
1answer
55 views

Theory of formal languages

How do i generate grammar for Prefix of Langauge L, SupposeG=(V,􏰀,P,S)is a context-free grammar generating a CFL L then pref(L) is defined as pref(L)={x∈􏰀∗ : ∃ y such that xy∈L}. I understand for ...
6
votes
1answer
125 views

If L is context-free, must FH(L) be context-free?

Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that } xy \in L\}$. In other words, $FH(L)$ is the set of first halves of even length strings in $L$. ...
1
vote
1answer
94 views

Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes [closed]

This is an extension of a previous question asked by a different user earlier: Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. ...
0
votes
1answer
121 views

Is Context Free Language closed under perfect shuffle?

Note that this is not shuffle but perfect shuffle, defined as follows: Let $w = a_{1}a_{2} \ldots a_{n}$ and $x = b_{1}b_{2} \ldots b_{n}$ be two strings of the same length. Then the perfect shuffle ...
2
votes
1answer
37 views

Is “duplicate” in RPN enough for replacing variable binding in term expressions?

I try to work out some consequences of storing (or "communicating"/"transmitting") a rational number by a term expression using the following operators: $0$, $\mathsf{inc}$, $\mathsf{add}$, ...
6
votes
1answer
219 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 ...
0
votes
0answers
77 views

Unrestricted grammar for a^n^2

I have a basic idea of how to generate an unrestricted grammar for a^2^n, a^3^n, or any a^c^n where c = constant. For a^2^n: S -> @aP P -> e P -> RP aR -> Raa @R -> @ @ -> e For a^3^n: S -> ...
0
votes
1answer
25 views

Kleene positive closure - help in proofing this claim

I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality. $ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+} $ Where: $ ...
0
votes
1answer
58 views

DFA for every run of a's=2 or 3

I am trying to create a dfa for L={w: every run of a's has length either two or three} this is my attempt at the solution..i feel like I am missing something..?
2
votes
1answer
33 views

Pumping lemma for 0^n and n>0

When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following: $S = 0^p$ $x = \varepsilon$ $y = 0^p$ $z = \varepsilon$ so $S = xyz = (\varepsilon)0^p(\varepsilon)$ For $x y^i z$ ...
1
vote
0answers
36 views

How to describe the language generated by S → a | S + S | S S | S * | ( S )

I am trying to solve the following problem from Aho, et al., Compilers: Principles, Techniques, & Tools (2nd ed.), exercise 2.2.2e: What language is generated by the following grammar? ...
2
votes
2answers
88 views

Show that 0^i where i is a power of 2 is not context free

I'm having difficulty trying to use the pumping lemma in order to show that $L= \{0^i \mid \ i \text{ is a power of 2 }\} $ is not context free. I"m starting by stating that $ s = 0^p$ and then $ s = ...
2
votes
1answer
35 views

Show that the string $( [ ) ]$ is not in a Dyck language

I think I understand why the string $( [ ) ]$ is not in a Dyck language. In my words, D2* is all the dyck words of 2 parentheses. From the definiton of $D2*$, every words must have exactly 2 ...
0
votes
1answer
40 views

Help understanding formal language notation

I am reading this text and it is making absolutely no sense to me. It as if it assumed I will understand. Not to mention the writer apparently had a book made and his grammar is poor. Some of the ...
0
votes
2answers
69 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language ...
2
votes
1answer
102 views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
-2
votes
1answer
30 views

Can every recursively enumerable language be defined with regular expression?

Can every recursively enumerable language be defined with regular expression? I came across this question, when studying for my test: Prove that for any finite language $L$, there is a Turing machine ...
0
votes
1answer
55 views

Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$

$L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$ How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a ...
3
votes
1answer
184 views

How to proof that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable. I know I can proof that language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts all ...
3
votes
2answers
260 views

complexity of determining whether a language given by context free grammar is empty

I know that it is decidable problem to check whether given context free grammar represents empty language -- for instance, AFAIR one could convert it to Chomsky normal form, and then check if any word ...