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

learn more… | top users | synonyms

1
vote
1answer
29 views

Constructing a NFA from a right linear grammar, is this correct?

Given the right linear grammar G S -> abA | bbB | a A -> bB | aA | b B -> baB | aaaA | [Epsilon/Terminates] Is the NFA in the image below the proper ...
1
vote
0answers
40 views

Difference between a*b and a*+b? Does the “+” denote Kleene plus or “or”?

Me and a friend are study for a quiz and are trying to determine the difference between the two NFA's produce by the regular exressions a*b and ...
0
votes
2answers
65 views

Designing a deterministic finite automata

How would I go about designing a deterministic finite automata to recognize the language L = {λ, ab, abab, ababab, . . . } consisting of strings that start with ‘a’, end with ‘b’, and alternate in ...
0
votes
1answer
48 views

Deterministic finite automata [closed]

For this question about Deterministic finite automata: Is this answer: bbbb, bbba, bbab, bbaa, b, a correct?
3
votes
1answer
137 views

Challenge on Some Language and PDA

Suppose We have Some language as follows: $L_1=\{w^* | w=x \text{ and } x \in \Sigma^*\}$ $L_2=\{ww^R ww^R | w \in ( \Sigma + \Sigma)^*\}$ $L_3=\{w | w=xy, x,y \in \Sigma^*, y \text{ is a ...
1
vote
1answer
30 views

Checking correctness of finite state automata designed

How to check correctness of finite state automata we have designed for a regular expression with the help of any computer program or prolog?
0
votes
1answer
31 views

Finite State Automata for (0+11+01)*(0)*(01)*

This is my homework problem and I am struggling hard for it. Can anyone please help me out? I need to find out finite state automata for (0+11+01) * (0) * (01)*. Also, if anyone can please tell me the ...
0
votes
1answer
27 views

Proving non-regularity of a language

How can I prove $L = (01^n2^n | n\geq 0)$ is not regular? Would it be sufficient to say that $01^p2^p$ is in $L$ and by pumping lemma, $01^p2^p$ can be written as $xyz$ such that $|y|>0, ...
0
votes
1answer
47 views

equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $ L= (ab \cup aab)^* $, what is the equivalence class for L? my professor ...
0
votes
2answers
92 views

Input and output of a Turing machine

For some machine models of computation there is no question what their input and output is: it's just the contents of some specific "cells", e.g. on a "tape" isomorphic to $\mathbb{N}$. Consider for ...
0
votes
1answer
27 views

Use the power-set construction to find a deterministic automata

Given a nondeterministc automata N, how do you use the power-set construction to find a deterministic automata that recognizes L(N)? Here is my work so far: We can start in state 1, 2. If we get ...
2
votes
1answer
26 views

Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
0
votes
1answer
40 views

how to draw this DFA?

{w belongs to all string patterns as a^i b^j a^k | i+j=even and j+k =odd} draw a DFA and find its regular language. please note here, i have put comma in between the format of aba string just for ...
0
votes
0answers
36 views

contradiction of pumping lemma on even palidrome language's completion

I have the language of all the words that are not even length palindromes, or more formally: $L= \{ w: \forall u\in\Sigma^*, w\ne uu^r \}$. And I need to prove that the Pumping Lemma for regular ...
0
votes
1answer
29 views

How can a DFA corresponding to an NFA have a transition that the original NFA does not?

First sorry for the poor pictures, but I think they are ok enough to get the point across. I would like to see the steps involved to convert this NFA to a DFA using the method explained in this ...
0
votes
1answer
15 views

Soft question, Understanding NFAs and DFAs; Requirements for either.

I have a few quick questions about NFAs and DFAs. Is any automaton with epsilon transitions always a NFA? Is any automaton with two paths for the same symbol from a state always a NFA? Ex. Say state ...
0
votes
0answers
104 views

DFA for language accepting odd number of a's and each a followed by at least 3 b's

I am creating a DFA for a language (over alphabets {a,b}) that accepts all strings containing "odd number of a's and each a followed by at least 3 b's" . This is what I've gotten so far with q4 as the ...
0
votes
2answers
21 views

Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
1
vote
2answers
26 views

Is a DFA a subset of NFA? Why?

After reading this previous question Difference between NFA and DFA, it's clearer to me their relationship/differences. Can one say that a DFA is a subset of a NFA where both recognize a/the same ...
0
votes
0answers
37 views

Number of states of a finite automaton recognizing all words beginning with some fixed string $x$

For a string $x \in \{a,b\}^\ast$ with $|x| = n$, how many states are required for an FA accepting the language of all strings in $\{a,b\}$ that begin with $x$? For each of these states, describe the ...
1
vote
1answer
9 views

Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
-2
votes
1answer
74 views

FA that accepts only those words that have an even number of substrings cdc?

I take this question as it could accept cdccdc,cdccdccdccdc,dddcdccdc,etc. I feel that I coveed all the even loops of cdccdc but I am stuck trying to figure out how to add in c* and d* in the mix of ...
0
votes
1answer
86 views

Turing Machine Problem

We know, A Turing machine is a hypothetical device that manipulates symbols on a strip of tape according to a table of rules I Draw a TM for input $x=(0+1)^*$ i want to implement ...
2
votes
1answer
31 views

$L=${$a^nb^nc^n : n \geq 0 $} CFG Recognizing

Suppose $L=${$a^nb^nc^n : n \geq 0 $} and I. $h(L), h(a)=a, h(b)=bb, h(c)=b$ II. $L^R$ III. $L^*$ IV. $h(L), h(a)=a, h(b)=bb, h(c)=a$ Why just I is a CFG and other is not? anyone can help me to ...
0
votes
2answers
76 views

Language of a grammar vs regular expression vs nfa

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
1
vote
1answer
25 views

context free grammar that describes even numbers

I am learning about context-free grammars and as a toy example I wanted to design one that describes binary digits ending with 0. My attempt : S -> 1S | 0S | e0 - where e is the empty string. Is this ...
-1
votes
1answer
57 views

PDA and Some language Grammar inference

L1={$w^* $| w=x and $ x \in \Sigma^*$} L2={$ww^R ww^R $| $ w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
0
votes
1answer
39 views

Pushdown Automata and Challenge in Grammar

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
1
vote
0answers
26 views

Lattice worms with nontrivial deaths

In Paterson's worms, a triangular lattice is used. A worm can move in 6 directions. As each node is hit, the worm follows an internal rule for which edge it will eat next based on the edges already ...
1
vote
1answer
52 views

Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
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
1answer
65 views

Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
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" ...
-1
votes
1answer
37 views

disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
1
vote
1answer
145 views

Complex automata Rubiks cube question (with picture) help needed

Question 1 A Rubik’s Cube is a puzzle in the shape of a cube. Each face is covered by nine stickers, each of which is coloured with one of six colours: white, red, blue, orange, green, andyellow. An ...
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 . ...
1
vote
1answer
77 views

$NP^{PP} vs. PP^{NP}$, which one subsumes the other?

I understand why P with an NP oracle ($P^{NP}$) subsumes $NP$: because it contains co-NP. But how about NP with a P oracle? Can it be any different from NP? (I'm guessing they are the same otherwise ...
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 ...
3
votes
1answer
75 views

Exponential objects in a category of abstract automata.

I'm working with a more or less standard definition of the category Aut(C) of automata over a category C (where C has finite products) which has tuples $$ A=\langle I_{A},O_{A},S_{A},\sigma_{A}, ...
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?
1
vote
2answers
39 views

NFA for $L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}$

Write an NFA to recognize the language $$L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}.$$ I'm not quite sure how to do this question. I don't know how to keep ...
1
vote
1answer
129 views

Turing machine for the language a^nb ^2nc^3n

How can we give a Turing Machines that accept following language. $$a^nb^{2n}c^{3n}$$ I am allowed to use also pseudo-code descriptions (i.e. high level descriptions of movements of r/w head):
1
vote
1answer
59 views

Deterministic Push-Down Automata

Does there exist Deterministic Push-Down Automata for the language below. Any kind of answer will be highly appreciated! $$L =ba^nb^n U bba^nb^{2n}$$
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 ...
2
votes
1answer
26 views

Stack automata with nonequality

I encontered the following problem that I'm unable to solve. The goal is to construct a stack automata, that accepts language $$ L = \left\{u\mathrm{\underline{c}}v \mid u,v \in ...