Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques

learn more… | top users | synonyms

0
votes
0answers
42 views

Every DPDA has an equivalent DPDA that always reads the entire input string

I am trying to understand the proof from Michael Sipser's Introduction to the Theory of Computation, page 132. I don't understand why if $q \in F′$ then $\delta(q,a,\$)$ is set to ...
0
votes
1answer
45 views

A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $ L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
0
votes
0answers
37 views

Language of Specific Grammar

I ran into this exercise in Sipser's Note on Computation Theory. Consider the following grammar $G$: $$\begin{align} S &\to aSD \;|\; bB \\ D &\to dS \;|\; a \\ B &\to bB \;|\; ...
0
votes
1answer
23 views

Algorithm that takes input desc. of two PDAs and outputs intersection of langs. recognized by two PDAs

Does there exist an algorithm which takes as input the descriptions of two pushdown automata, $P1$ and $P2$, and prints the description of another pushdown automaton which recognizes the intersection ...
0
votes
1answer
19 views

Deciding TM which fails to halt whenever the length of its input string is a prime number

I have the following Statement: "A TM called $A$ which fails to halt (i.e runs forever) whenever the length of its input string is a prime number, and eventually halts for all other input strings" ...
0
votes
0answers
28 views

Design an finite automata for 010 and 01? [duplicate]

I have tried below question for designing automata but didn't success . ...
0
votes
0answers
13 views

What are the classes in A.N. Maslov hierarchy of indexed languages corresponding to Chomsky Hierachy?

As we know,that classes in A.N. Maslov hierarchy of indexed languages of level 2 is in sensitive languages of Chomsky hierarchy. What are the classes in A.N. Maslov hierarchy of indexed languages ...
0
votes
0answers
23 views

Do automatons and formal grammars belong to formal systems

A formal system consists of a formal language, a formal grammar that generates the language, a set of axioms, and a set of inference rules. Are automatons also formal systems? Is an automaton ...
0
votes
0answers
124 views

How to check whether a language is regular or not?

Say I have a given expression like $L_1\{a^n\mid n\ge0\}$ $L_2\{b^n\mid n\ge 0\}$ Then what is the procedure of checking weather L1.L2 is regular or not?
0
votes
1answer
31 views

How does the push-down automaton have to look like?

Could you give me a hint how to find a push-down automaton for the language: $$L=\{ a^n b^{2n} | n \in \mathbb{N}\}$$ How does the push-down automaton have to look like?
0
votes
0answers
16 views

Struggling to prove Markov chain property / State machine property - I can see what I need to do just can't write it

First notation, I have created the shorthand: $$P_x(A)=\mathbb{P}(A|X_0=x)$$ just to save time. I wish to prove "Lemma 1.3" which states the following: If $0<\alpha\le P_x(T_y\le k) \forall x\in ...
0
votes
1answer
30 views

minimal DFA with four states

I want to minimal this DFA: But i don't know what to do. Anyone can help me? Thanks
0
votes
1answer
48 views

What did the proof by diagonalization actually disprove?

http://www.cse.ohio-state.edu/~gurari/theory-bk/theory-bk-fourse5.html I sort of understand the proof, but is it showing that some language are undecidable? If so, what language exactly? Because each ...
0
votes
0answers
41 views

CFG Convertion to GNF

I have a very simple CFG that I am trying to convert into GNF. The CFG is: S -> aSbS S -> epsilon I looked at the CFG and I think I can just do the ...
0
votes
1answer
60 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
66 views

turing machine accept and reject state

I am pretty new to Turing Machines and I am trying to understand the basic things first...so my question is , would this machine accept all words ending in 'a' ? if ...
0
votes
0answers
54 views

how do I make this post machine accept aab or baa?

so far I made it accept, a, aaa,bab but now I want strings aab or baa. How would I do this ? this is what I have so far... edit: @Hagen von Eitzen here is the example of Post Machine that a lot of ...
0
votes
0answers
46 views

Is the language $L = \{0^m1^n: m \neq n \}$ not context free?

I have been trying to prove that this is not a context free language using the pumping lemma for CFLs. I have tried for hours but am not able to prove it. Is it a context free language or not? How to ...
0
votes
2answers
38 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 ...
0
votes
2answers
62 views

Pushdown Automata

I having trouble constructing NPDAs for these two languages: $L_1 = \{a^nb^m \mid 2n \le m \le 3n\}$ $L_2 = \{a^nb^mc^k \mid n = m \: or \: m \ne k\}$ Would these be the proper states for the first ...
0
votes
0answers
32 views

Context-free languages

Is the following language context-free? $\{ w \in \{a,b,c\}^* : (\#_a(w) - \#_b(w)) \cdot \#_c(w) = \#_b(w)$ and all c's are encountered before any a$\}$. $\#_a(w)$ = amount of a's in w Thanks in ...
0
votes
1answer
20 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 ...
0
votes
1answer
22 views

Are these two languages equivalent?

$L = \{w \in \{a,b\}^{*}$ such that $w = R(w)\}$ R(w) = the reverse of w $L = \{u \in \{a,b\}^{*}\}$ If not can you draw a pda or define a grammar for each? I don't see how they could have ...
0
votes
0answers
72 views

how to convert Finite Automata into Push Down Automata

I am trying to convert Finite Automata into Push Down Automata and I am not sure if I am doing this right. There are not many good tutorials on this topic that I can find, but this is what I have. I ...
0
votes
0answers
41 views

Cartesian product of a DFA and PDA

I am just wondering how to do it. I am not quite sure if this is the right way. 1) Write down all the combination of states. 2) Take into consideration the "input" side of the DFA and write the ...
0
votes
0answers
23 views

Designing a pushdown automata

I think I realized something, but I am not sure. So what I think I've realized is that if you have to design a L such that it accepts any string with the same amount of 1 and 0. You need 2 states: ...
0
votes
1answer
38 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 ...
0
votes
0answers
37 views

Is this grammar ambiguous?

$S > SS|10|0$ $S > SS > SSS > 0SS > 00S > 000$ $S > SS > 0S > 0SS > 00S > 000$ $2$ leftmost derivations
0
votes
0answers
33 views

Relationship between pushdown automata and CFG

I thought that pushdown automata and CFG were separate things in that one was the graphical expression of the other, but I saw a pushdown automata that uses CFG terms such as epsilon, S, S->1S0, or ...
0
votes
1answer
41 views

Proving that a language having a particular CFG grammar is equivalent to a particular L

I think we need to prove that L(G) is a subset of L and then we need to prove that L is a subset of L(G). For the first part, I think we need to say for any w in L(G) we have an even number of as ...
0
votes
1answer
22 views

Pumping lemma clarifications

http://www.cs.oberlin.edu/~asharp/cs383/handouts/pumping.pdf I came across this and realized that what some people told me was completely wrong. We get to choose xyz, but the demon choose uvw and uvw ...
0
votes
1answer
72 views

How do we choose a good string for the pumping lemma?

we have a Language $$\mathscr L: \{a^mb^n: m \ne n\}$$ we need to choose a good string $w$. apparently $w = a^{n+1}m^{n}$ is not a good string. can someone explain why? I also found this and I ...
0
votes
1answer
47 views

Struggling with Proof Writing. Simple question for demostration.

I am practicing writing proofs over regular expressions. Here is the question: Show that $(r\cup \varepsilon)^*= r^*$, where $r$ is a string. Intuitively, the left hand side is the concatenation of ...
0
votes
1answer
244 views

Context free grammar to pushdown automata…

<expr> −→ <term> | <expr> + <term> <term> −→ <factor> | <term> × <factor> <factor> −→ (<expr>) | b ...
0
votes
1answer
27 views

If the language is context free?

i believe intuitively the following language is CF. But there is a book (without more description) that states the language is not CF. If I'm in a wrong way? $L=\{W_1cW_2 | W_1,W_2 \in (a+b)^* W_1 ...
0
votes
2answers
40 views

What method should you follow to show what a DFA does?

I'm specifically looking for help analyzing the following DFA. What steps would one follow to show what language this particular DFA accepts? To me it seems quite random, and I can't figure out a ...
0
votes
0answers
58 views

Is the PDA I drew correct?

Could you tell me if the language $L=\{a^{m}b^{n}:m \neq n,m>0,n>0 \} $ is accepted by the following pushdown automaton, where the alphabet of the stack is $\{a,z\}$ and $z$ is the initial ...
0
votes
2answers
58 views

Determining whether a language belongs to R or RE (Turing Machines)

Does the language L belong to R, RE or neither? In each case, why? Thanks a lot!
0
votes
1answer
50 views

build finite automaton for language minimize states

I want to build a finite automaton that accepts $a^nb^n, n \gt 0, m \ge 0$. I can't do it unless the FA has two final states, i.e.: $delta(q0, a) = q1 delta(q1, a) = q1 delta(q1, b) = q2 delta(q2, ...
0
votes
0answers
39 views

Context-sensitive grammar for this language

In order to write a context-sensitive grammar for: $L = \{ a^{n} b^{n} c^{n} d^{n} : n \ge 1 \}$ One possible set of productions is: $S \rightarrow aBCd | abcd $ $aB \rightarrow aaBb | ab | ...
0
votes
1answer
47 views

Assign Integer to Each Turing Machine

I have the following problem: suppose that we have an infinite set of symbols, $A = \{a_1, a_2, ...\}$ from which all Turing Machine input alphabets are chosen. Show how we could assign an integer to ...
0
votes
2answers
35 views

Turing decidable/undecidable

let $X = \{\langle M \rangle\ |\ M\text{ is a finite state machine and }L(M) = \emptyset\}$ where $\langle M \rangle$ is an encoding of the machine $M$. can you prove whether $X$ is Turing ...
0
votes
0answers
30 views

Is this a context-free language?

Let $L = L_1^* \circ L_2^*$ where $L_1 = \{1^n 0^m 1^n : n,m \in \Bbb N\}$ and $L_2 = \{0^m 1^{2m} : m \in N\}$. Is the language $L$ a context free language? I think I can write automata for $L_1$ ...
0
votes
0answers
34 views

How to write a Regular Expression

I have seen that the regular expression for the set of strings beginning with a and ending with b is written as a(a+b)*b Can some one tell me how to write this
0
votes
1answer
197 views

Grammar Construction from Given Language!

Just a fast question! I have this language L(G) = { z^n * x^2n with n>=1 } What is the grammar ? I think it should rather be: ...
0
votes
2answers
43 views

Building an automaton that defines a language

I have $2$ languages, $L_1$ and $L_2$, both are part of $L$-dfa. I have the following language: $$L_0= \{a_1\cdot b_1\cdot a_2\cdot b_2\cdot\ldots a_n\cdot b_n \mid a_i,b_i\in\Sigma, ...
0
votes
1answer
25 views

Binary Comparison using automata

The question is: Construct a DFA, which accepts the following language, $\{\omega | \omega = a_1b_1a_2b_2...a_nb_n\}$ for some n, where $b_i, b_i\in \{0, 1\}$ and $a_1a_2...a_n > b_1b_2...b_n$ I ...
0
votes
0answers
102 views

Formal Languages: String Notation

In formal languages, we usually denote an alphabet $\Sigma$ as the set of symbols it contains, e.g. $\Sigma = \{0,1\}$ is the binary alphabet. It can be confusing because we denote $\Sigma^1$, the ...
0
votes
1answer
32 views

Give an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct.

Given an example of a language $L \subset \{0,1\}^*$ such that rows of the matrix $T_L$ are distinct. We define the matrix as follows. Let $L \subset \Gamma^*$ where $\Gamma$ is alphabet. Then the ...
0
votes
1answer
31 views

Construc a DFA for given language

The given language is this. $$L = \{a^nb : n \geq 0\}$$ Let $M = \left<\{q_0,q_1,q_2\},q_0,\Gamma=\{a,b\},\delta,\{q_2\}\right>$ be a DFA, where $q_0$ is the initial state, $q_2$ is the accept ...