Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

1
vote
1answer
33 views

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$ My first intuition is "Yes", since we may look at $M_1, M_2$ which accepts $L_1, L_2$, respectively. Then, WLOG there's $w$ such ...
8
votes
2answers
164 views

Regularity of unary languages with word lengths the sum of two resp. three squares

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ ...
0
votes
1answer
48 views

Proving a language isn't regular using the pumping lemma

Let the language $$ L = \{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \} $$ Show that $L$ isn't regular using the pumping-lemma. Let's assume by contradiction ...
-1
votes
1answer
25 views

union of two equivalence classes (Myhill–Nerode theorem)

Let a language, $L$ such that the equivalence relation, as defined in Myhill–Nerode theorem has $4$ equivalence classes; $A_1, \ldots, A_4$. Let $S = A_1 \cup A_2$. Is $S$ always regular? ...
0
votes
1answer
38 views

Proof that a language is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
1
vote
0answers
34 views

Formal language properties and finite state machines [on hold]

What are properties of a formal language? Which and how would they be needed to prove that some Non-Deterministic finite state machine can accept a given language?
1
vote
0answers
24 views

How many restricted length strings are there without significant repetitions

Let us fix an alphabet $\Sigma$ of size $c$, then we have the finite language $\Sigma^n$ which is the set of all $n$ length words. For each $N,M$ how many words are there in $\Sigma^n$ such that no ...
-3
votes
1answer
37 views

What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$ What is the minimal number of states for a DFA, accepting $L$? ...
1
vote
1answer
31 views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
2
votes
3answers
137 views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
2
votes
2answers
36 views

Prove/ Disprove: If $L$ is a CFL then $A(L)$ is a CFL too

Consider the operation $A(L)$: $$A(L) = \{ w: w\in L \land w_R \notin L \}$$ where $w_R$ is the reverse of $w$. Prove/ Disprove: if $L$ is a CFL language so does $A(L)$. I am almost certain ...
-1
votes
0answers
9 views

how to send parameters vb to java [closed]

I have a code in visual basic which catch keystrokes, how can I send the strokes as string parameters to other java program which I made in order to print them? ( how can I send parameters ...
1
vote
1answer
30 views

Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?

I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be ...
-1
votes
0answers
28 views

Statments about recursive and recursively enumerable languages [closed]

I need help with proof of the following statements: If L1, L2 are recursive and L3=L1-L2 then L3 is also recursive. I know that there is TM1 which accept\reject any word of L1 and there is TM2 ...
0
votes
1answer
21 views

Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA: I prepared below tables and finally the NFA: NFA However I feel I am wrong here, since original NFA does not have any transitions defined for state C ...
5
votes
1answer
72 views

Closure properties of linear context-free languages

Under what operations are linear context-free languages closed? Suppose $L_1, L_2$ are two linear context free languages. Are there any guarantees about $L_1 \cup L_2$, $L_1 \cap L_2$, ...
-1
votes
1answer
45 views

Prove Language Is Union of Fninitely Many Arithmetic Progressions [closed]

So, you see in the image the question and its answer (proof below the black line). I get the entire proof until the last formula. It basically says that if length of a string is larger than number of ...
1
vote
1answer
30 views

Converting a NFA to its equivalent regular expression

I'm new to regular expressions and I'm currently working on some exercises on converting DFA's and NFA's into their equivalent regular expressions. I have the following NFA: I'm using the state ...
-1
votes
0answers
32 views

Describe a PDA for the language [duplicate]

Let the language $$ L = \left\{ w\in\Sigma^* : w\neq xcx \text{ for any } x\in\{a,b\}^* \right\}\,. $$ Show a PDA that accepts the language. I'd be glad to get a guidance. I've heard about a ...
0
votes
1answer
37 views

algoritm to convert a monoid into an automaton [closed]

In literature, is there an algoritm to convert a monoid into an atomaton? I am looking for references/applications.
0
votes
2answers
55 views

Identifying and describing the language accepted by a Turing machine [closed]

Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?
6
votes
3answers
223 views

Relationship between formal system and formal languages

In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems. ...
0
votes
2answers
55 views

simulation of PDA with turing machine

How to simulate a non-deterministic PDA with a turing machine?
2
votes
1answer
20 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 ...
-2
votes
0answers
16 views

Show language of binary sums is not regular [closed]

Let $\Sigma = \{0, 1, +, =\}$ and $$ ADD = \{x = y + z\mid x, y, z \in \Sigma^* \text{ and $x$ is the sum of $y$ and $z$}\} $$ Where addition is interpreted as binary addition. For example, the ...
0
votes
0answers
38 views

Formalizing T-diagrams [closed]

T-diagrams (short for Tombstone diagrams) are used to illustrate language transformations. Let $T(A,B,C, I, O)$ be the relation which represents the T-Diagram for $A$, $B$, $C$, $I$, and $O$, meaning ...
0
votes
1answer
46 views

Infinite u decidable languages

I am trying to see if infinite languages are always decidable. I believe it is not always decidable because there will not be a maximum length of string for the Turing machine to halt. Am I on the ...
2
votes
1answer
36 views

prove that a language is context free given a regular language

R is a regular language over $\Sigma=\{0,1\}$ $Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$ I need to prove that Sub(R) is context free. I know that the quotient of a context free language with a ...
0
votes
2answers
58 views

Find a pushdown automaton for $ \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$

I was told to built a PDA that recognizes the following language: $$L = \{x\#y \mid x,y \in \{0,1\}^{\ast} \wedge x \neq y\}$$ My attempt is basically to push $x$ to the stack for every $1$ and $0$ ...
1
vote
1answer
25 views

How to create this pushdown transducer? (formal languages and automata)

Create a pushdown transducer that translates $a^m b^{2m}c^{m+n}$ into $b^{n-m}$, with $n\geq m \geq 0$. How should I use the stack to remember or to compute how many characters of c to read? And how ...
1
vote
1answer
30 views

Rational subsets of a monoid

In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the ...
3
votes
1answer
39 views

Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular? My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number ...
0
votes
2answers
72 views

Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular [closed]

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$ I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping ...
2
votes
1answer
47 views

Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

Consider the language below, on the alphabet $\Sigma = \{a,b,\$\}$: $$L = \left\{ x$y \mid x,y\in\{a,b\}^* \land \left|x\right| \ne \left|y\right| \right\}$$ I need to define a CFG for this language. ...
2
votes
1answer
218 views

Can a recursive language be uncountable?

Does there exist a recursive language $L$ whose cardinality is uncountable? I would like to have an explanation whether Turing Machine can encode uncountable languages and whether we can use this to ...
2
votes
2answers
115 views

Context Free Grammar for $a^*b^*c^* - \{a^n b^n c^n \mid n \geq 0 \}$ [duplicate]

I'm having trouble constructing a Context Free Grammar for the following language: $$a^{\ast}b^{\ast}c^{\ast} - \{a^{n} b^{n} c^{n} \mid n \geq 0 \}$$ I believe it's telling me that no string can be ...
2
votes
2answers
132 views

Automatic translation between formal languages

There are parser generators (some of which are limited to certain classes of grammars) which, given a grammar, automatically generate a parser for that grammar. Would it be possible to make a ...
0
votes
1answer
43 views

Proving that non-regular languages are closed under concatenation

How can I prove that non-regular languages are closed under concatenation using only the non-regularity of $L=\{a^nb^n|n\ge1\}$ ?
5
votes
2answers
31 views

Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input ...
0
votes
1answer
46 views

Confusing example of a language which may be Context-free or not context-free

Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n ...
2
votes
2answers
41 views

Ambiguous context free

Is there any technique to prove that a given language L is not ambiguous context-free? Here I don't know that whether L is CFL or not.
5
votes
0answers
51 views

Calculating with regexes

We use a regex engine (say, PCRE) that allows grouping subexpressions with parentheses and recalling the value they match in the search / replace expressions (backreferences, denoted by \i for ...
1
vote
2answers
75 views

Prove if given language is regular or not

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$ To Prove: If given language is regular or not. I know that it is not a regular language but I am not able to come up with the string which I can ...
0
votes
1answer
26 views

If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable?

I am discussing with a friend the following question: If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable? I believe it is. My point ...
3
votes
1answer
53 views

A non-regular language satisfying the pumping lemma

I got a problem to solve, which is to demostrate that the language $L$, given by: $L = \{ab^nc^n\mid n \geq 0\} \cup \{a^kw \mid k\geq 2 \wedge w \in \Sigma^*\}$ Satisfies the pumping lemma. Is not ...
0
votes
0answers
43 views

The pumping lemma for the context free languages [duplicate]

I am trying to use the pumping lemma to show this is not a context free language $$ L = \{a^n b^{2n} a^n\mid n\ge 0\} $$ My idea is fist assume it is a CFG language and let $n$ be the pumping lemma ...
0
votes
2answers
50 views

Transforming NFA into DFA

In the examples I was given I have the following NFA diagram: Then it gives the conversion process Could someone explain to me the process of obtaining the second column: {1,2,4} = a{1, 2, 3, 4}, ...
2
votes
1answer
82 views

show that language $L'$ is regular (given $L$ regular)

I am working on the following question: $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular. Firstly I show my idea. When you accept it I will try to ...
1
vote
0answers
54 views

How to draw a clearly arranged DFA of a language with modulo rules?

I know how to draw a DFA, but I have problems with this specific one: ${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$ This language is regular and there has to exist a ...
1
vote
0answers
18 views

Are deterministic context-free languages closed under reversal of languages? [duplicate]

It is well known that context-free languages are closed under the reversal of $L$. My answer to the question "Is the time reversal symmetry of non-deterministic computations important?" notices that ...